Кратко — критерий: все заданные точки должны быть экстремальными (vertices) выпуклой оболочки множества; эквивалентно — их множество совпадает с множеством вершин выпуклой оболочки (и при требовании «вершины» — ни одна точка не лежит строго внутри или на отрезке между двумя других вершин).
1) Формулировки/критерии
- Точка $p$ экстремальна ⇔ не существует представления $p={\sum }_{i\ne p}{\lambda }_i{x}_i$ с ${\lambda }_i\ge 0,\sum {\lambda }_i=1$.
- Набор точек в «выпуклой позиции» ⇔ ни одна точка не лежит внутри выпуклой оболочки остальных.
- Практически: вычислить выпуклую оболочку $H$ множества; если множество вершин $H$ совпадает с исходным множеством (и, при строгом требовании на вершины, на $H$ нет коллинеарных внутренних точек на ребрах), то ответ — да.
2) Полный алгоритм (рекомендованный)
- Удалить дубликаты; пусть $n$ — число оставшихся точек.
- Построить выпуклую оболочку (например, алгоритм Andrew / monotone chain или Graham scan), получив упорядоченный список вершин $H$.
- Для вычисления ориентации троек точек $(a,b,c)$ используйте знак векторного произведения
$$\text{orient}(a,b,c)=(b_x-a_x)(c_y-b_y)-(b_y-a_y)(c_x-b_x).$$ Положительный знак — левый поворот, отрицательный — правый, ноль — коллинеарны.
- Сравнить размеры: если $|H|=n$ и при этом для всех соседних троек вершин $\text{orient}\ne 0$ (нет коллинеарных подряд точек), то все точки являются вершинами минимальной по включению выпуклой оболочки. Иначе — нет.
3) Варианты алгоритмов и сложности
- Andrew (monotone chain) или Graham scan: построение оболочки за $O(n\log n)$ (сортировка по x/углу) и затем линейная постройка. Общая сложность $O(n\log n)$.
- Gift wrapping (Jarvis march): $O(nh)$, где $h=|H|$. Хорошо, когда $h$ мало, худший случай $O(n^2)$.
- Chan’s algorithm: $O(n\log h)$ — оптимально при малом $h$.
- Quickhull: обычно $O(n\log n)$ на практике, но худший случай $O(n^2)$.
- Альтернатива для верификации, если дано предполагаемое упорядочение вершин: сортировка по углу вокруг внутренней точки + проверка ориентаций всех подряд троек — итого $O(n\log n)$ (сортировка) и затем $O(n)$ проверок. Если упорядочение уже есть — проверка за $O(n)$.
4) Замечания по коллинеарности
- Если допускаются точки, лежащие на ребрах (коллинеарные между двумя «угловыми» вершинами), то такие точки не считаются вершинами минимальной по включению оболочки. Чтобы учесть это, при построении оболочки можно настроить алгоритм на исключение коллинеарных внутренних точек (например, при Andrew при равенстве ориентации удалять среднюю точку).
Вывод: самый простой и надёжный путь — построить выпуклую оболочку (Andrew/Graham) за $O(n\log n)$ и проверить равенство множеств вершин; при необходимости использовать Jarvis/Chan для специальных случаев (мало вершин).