Алгоритмы построения выпуклой оболочки (Glikjnmbd hkvmjkyunx fdhrtlkw kQklkctn)
В вычислительной геометрии существует много алгоритмов нахождения выпуклой оболочки конечного множества точек с разной сложности вычислений.
Область называется выпуклой, если отрезок, соединяющий произвольную пару ее точек, целиком лежит в этой области. Вычислить или построить выпуклую оболочку означает, что будет выполнено четкое и эффективное представление необходимой выпуклой формы. Вычислительная сложность соответствующих алгоритмов обычно рассчитывается в терминах n - число входных точек, и h - числа точек в выпуклой оболочке.
Плоский случай
[править | править код]Рассмотрим общий случай, где входными данными алгоритма является конечное неупорядоченное множество точек декартовой плоскости. Важным частным случаем, в котором точки приведены в порядке обхода границы простого многоугольника описывается ниже в отдельном подразделе.
Литература
[править | править код]На русском языке
[править | править код]- Дж.Макконнелл. Анализ алгоритмов. Активный обучающий подход (3-е издание). — Москва: Техносфера, 2013. — 416 с. — ISBN 978-5-94836-216-8.