Выпуклая оболочка

Материал из Algocode wiki
Перейти к: навигация, поиск

Определения

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


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


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

Задача

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

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

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

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

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

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



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

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