Выпуклая оболочка: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
Строка 26: Строка 26:
  
 
{{Автор|Глеб Лобанов|glebodin}}
 
{{Автор|Глеб Лобанов|glebodin}}
 +
 +
[[Категория:Конспект]]

Версия 21:24, 8 мая 2020

Определения

Выпуклое множество - такое множество точек, что все точки отрезка, образуемого любыми двумя точками данного множества, также принадлежат данному множеству


Выпуклая оболочка фигуры - такое выпуклое множество точек, что все точки фигуры также лежат в нем.


Минимальная выпуклая оболочка фигуры - это минимальная по площади выпуклая оболочка.

Задача

Дано множество точек, требуется построить его минимальную выпуклую оболочку.

Алгоритм Джарвиса(Метод заворачивания подарка)

Алгоритм Грэхема

Алгоритм Эндрю

Дополнительно

Алгоритм Чана

Онлайн выпуклая оболочка



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin