Алгоритмы построения выпуклой оболочки

В вычислительной геометрии существует много алгоритмов нахождения выпуклой оболочки конечного множества точек с разной сложности вычислений.

Область называется выпуклой, если отрезок, соединяющий произвольную пару ее точек, целиком лежит в этой области. Вычислить или построить выпуклую оболочку означает, что будет выполнено четкое и эффективное представление необходимой выпуклой формы. Вычислительная сложность соответствующих алгоритмов обычно рассчитывается в терминах n - число входных точек, и h - числа точек в выпуклой оболочке.

Плоский случай

Рассмотрим общий случай, где входными данными алгоритма является конечное неупорядоченное множество точек декартовой плоскости. Важным частным случаем, в котором точки приведены в порядке обхода границы простого многоугольника описывается ниже в отдельном подразделе.

Литература

На русском языке

• Дж.Макконнелл. Анализ алгоритмов. Активный обучающий подход (3-е издание). — Москва: Техносфера, 2013. — 416 с. — ISBN 978-5-94836-216-8.