Применения выпуклых оболочек

Перед тем, как научиться строить выпуклые оболочки, разберем несколько задач, которые можно решать с их помощью.

В этой статье сильно недостает иллюстраций, но мы надеемся на ваше воображение.

#Локализация точки

Пусть у нас есть выпуклый многоугольник $A_0 A_1 A_2 \ldots A_n$ и поступают запросы определить, находится ли точка $P$ внутри него.

Рассмотрим его триангуляцию на треугольники $\Delta A_0 A_1 A_2, \Delta A_0 A_2 A_3, \ldots, \Delta A_0 A_{n-1} A_n$ и решим чуть более сложную задачу: определить, к в каком их треугольников она лежит (если она вообще лежит внутри многоугольника).

Рассмотрим вектора $\overrightarrow{A_0 A_1}, \overrightarrow{A_0 A_2}, \ldots, \overrightarrow{A_0 A_n}$ — диагонали, разбивающие многоугольник на треугольники. Заметим, что они отсортированы по углу — для определенности будем считать, что против часовой стрелки. Рассмотрим вектор $\overrightarrow{A_0 P}$ и найдем в этой последовательности из $n-1$ векторов первый, который находится «справа» от $\overrightarrow{A_0 P}$. Это можно сделать бинарным поиском и проверкой через знак векторного умножения.

Пусть мы нашли такое $1 \leq i < n$, что вектор $\overrightarrow{A_0 P}$ зажат между $\overrightarrow{A_0 A_i}$ и $\overrightarrow{A_0 A_{i+1}}$. Тогда просто проверим, попала ли точка $P$ в треугольник $\Delta A_0 A_i A_{i+1}$ или нет. Если попала, то точка $P$ лежит внутри многоугольника и мы локализовали ее положение, иначе точка $P$ лежит снаружи многоугольника.

Каждый такой запрос мы обрабатываем за время $O(\log{n})$.

#Поиск касательных, параллельных данной прямой

Пусть у нас есть выпуклый многоугольник и некоторая прямая. Мы хотим найти $2$ прямые, которые касаются многоугольника и при этом параллельны данной прямой.

Найдем точки, в которых эти прямые будут касаться многоугольника. Рассмотрим вектор $v$ — направляющий вектор данной прямой. Рассмотрим вектора $\overrightarrow{A_0 A_1}, \overrightarrow{A_1 A_2}, \ldots, \overrightarrow{A_n A_0}$ — напомним, что вершины идут в порядке против часовой стрелки, а значит эти вектора будут отсортированы по полярному углу.

Тогда, если рассмотреть, между какими соседними позициями в этом порядке должны находиться вектора $v$ и $-v$, то эти позиции будут соответствовать тем вершинам, в которых касательные касаются многоугольника. Для того, чтобы найти эти позиции, достаточно сделать lower_bound по последовательности векторов.

#Поиск касательных из точки

Пусть у нас опять есть выпуклый многоугольник $A_0 A_1 \ldots A_n$, но прямой нет, а есть некоторая точка $P$. Мы хотим найти $2$ точки $A_i$ и $A_j$, такие что прямые $P A_i$ и $P A_j$ это касательные к многоугольнику — или сказать, что точка $P$ лежит внутри многоугольника.

Проводить проверку мы уже умеем за $O(\log n)$, так что предположим, что точка лежит снаружи.

Рассмотрим такую же последовательность ориентированных векторов-ребер и разделим её на две половины: будем называть ребро $A_i A_{i+1}$ левым, если точка $A_{i+1}$ лежит слева от прямой $P A_i$, иначе правым.

Дальше мы можем запустить от левой половины бинпоиск, который будет искать первую вершину $A_i$, для которой $A_{i+1}$ лежит справа от вектора $P A_i$ — ровно этой вершины и будет касаться касательная. Бинпоиск в правой половине делается аналогично.

#Пара наиболее отдаленных точек

Дан набор $n$ точек, и требуется найти среди них пару наиболее отдаленных.

Заметим, что оптимальная пара гарантированно лежит на выпуклой оболочке этого множества: если бы одна из точек лежала строго внутри выпуклой оболочки, то можно было бы вместо неё выбрать какую-то более отдаленную.

Построим выпуклую оболочку всех точек и пронумеруем её вершины в порядке обхода против часовой стрелки. Заметим, что если для $l$-той точки самой отдаленной была $r$-тая, то для $(l+1)$-ой и всех дальнейших никакая точка раньше $r$-той в обходе не может быть оптимальной.

Здесь возникает идея применить метод двух указателей: будем перебирать точку $l$ в оболочке и поддерживать оптимальную $r$ для неё, в цикле while проверяя, лучше ли получатся ответ для пары $l$ и $(r+1)$. Так как суммарно $r$ сделает не более $O(n)$ увеличений, алгоритм будет работать за $O(n)$ плюс время построения выпуклой оболочки.

#Треугольник максимальной площади

Дан набор $n$ точек, и требуется найти среди них треугольник с максимальной площадью.

Аналогично предыдущей задаче, все три точки гарантированно будут на выпуклой оболочке, так что сразу построим её.

Теперь заметим, что для фиксированного основания $a$ и $b$, если мы увеличим его правую точку, то оптимальная третья точка $c$ будет иметь не меньший номер.

Значит, мы можем перебрать точку $a$, а затем с помощью метода двух указателей перебрать $b$, поддерживая оптимальный $c$. Суммарно алгоритм будет работать за $O(n^2)$.