Введение

Семейство задач в вычислительной геометрии

Задача определения положения точки является фундаментальной темой в вычислительной геометрии. Она находит применение в областях, связанных с обработкой геометрических данных: компьютерная графика, географические информационные системы (ГИС), планирование движения и системы автоматизированного проектирования (САПР). В своей наиболее общей формулировке, задача состоит в том, чтобы, при заданном разбиении пространства на непересекающиеся области, определить, в какой области находится заданная точка запроса. Например, задача определения, в каком окне графического пользовательского интерфейса произошел клик мышью, может быть сформулирована как частный случай задачи определения положения точки, где разбиение формируется видимыми частями каждого окна, хотя для этого приложения специализированные структуры данных могут оказаться более подходящими, чем универсальные структуры данных для определения положения точки. Другим частным случаем является задача «точка в многоугольнике», в которой необходимо определить, находится ли точка внутри многоугольника, снаружи его или на его границе. Во многих приложениях требуется определить положение нескольких различных точек относительно одного и того же разбиения пространства. Для эффективного решения этой задачи полезно построить структуру данных, которая, получив точку запроса, быстро определяет, в какой области она находится (например, диаграмма Вороного).

Плоскость

В плоском случае нам дано плоское разбиение S, образованное множеством многоугольников, называемых гранями, и требуется определить, какая грань содержит заданную точку запроса. Возможен прямой перебор всех граней с использованием алгоритма «точка в многоугольнике», но для разбиений высокой сложности это обычно нецелесообразно. Различные подходы приводят к оптимальным структурам данных, требующим O(n) памяти для хранения и O(log n) времени для запроса, где n — общее количество вершин в S. Для упрощения предположим, что плоское разбиение находится внутри квадратной ограничивающей рамки.

Разложение шлаков

Самая простая и ранняя структура данных для достижения временной сложности O(log n) была обнаружена Добкином и Липтоном в 1976 году. Она основана на разбиении S с использованием вертикальных линий, проходящих через каждую вершину в S. Область между двумя последовательными вертикальными линиями называется полосой. Обратите внимание, что каждая полоса разделена непересекающимися отрезками, которые полностью пересекают полосу слева направо. Область между двумя последовательными отрезками внутри полосы соответствует уникальной грани S. Таким образом, мы сводим задачу определения положения точки к двум более простым задачам:

Для заданного разбиения плоскости на вертикальные полосы, определить, какая полоса содержит данную точку. Для заданной полосы, разбитой на области непересекающимися отрезками, которые полностью пересекают полосу слева направо, определить, какая область содержит данную точку. Первая задача может быть решена с помощью бинарного поиска по x-координате вертикальных линий за время O(log n). Вторая задача также может быть решена за время O(log n) с помощью бинарного поиска. Чтобы понять, как это работает, заметим, что поскольку отрезки не пересекаются и полностью пересекают полосу, отрезки можно отсортировать по вертикали внутри каждой полосы. Хотя этот алгоритм позволяет определять положение точки за логарифмическое время и его легко реализовать, объем памяти, необходимый для построения полос и областей внутри них, может достигать O(n²), поскольку каждая полоса может пересекать значительную часть отрезков. Несколько авторов заметили, что отрезки, пересекающие две смежные полосы, в основном одинаковы. Следовательно, размер структуры данных можно значительно уменьшить. В частности, Сарнак и Тарян проводят вертикальную линию l слева направо по плоскости, поддерживая отрезки, пересекающие l, в постоянном красно-черном дереве. Это позволяет им уменьшить объем памяти до O(n), сохраняя при этом время запроса O(log n).

Монотонные подразделения

(Вертикальная) монотонная цепь — это путь, вдоль которого y-координата никогда не возрастает. Простой многоугольник является (вертикально) монотонным, если он образован двумя монотонными цепями, имеющими общие первую и последнюю вершины. Можно добавить некоторые ребра к планарному разбиению, чтобы сделать все грани монотонными, получив так называемое монотонное разбиение. Этот процесс не добавляет новых вершин к разбиению (следовательно, размер остается O(n)), и может быть выполнен за время O(n log n) с помощью сканирующей прямой (также может быть выполнен за линейное время, используя триангуляцию многоугольника). Поэтому без потери общности мы можем ограничить нашу структуру данных случаем монотонных разбиений, как это делается в данном разделе. Недостатком разложения на полосы является то, что вертикальные линии создают дополнительные сегменты в разложении, что затрудняет достижение пространства хранения O(n). Герберт Эдельсбруннер, Леонид Гвибас и Хорхе Столфи обнаружили оптимальную структуру данных, которая использует только ребра монотонного разбиения. Идея заключается в использовании вертикальных монотонных цепей вместо вертикальных линий для разделения разбиения. Преобразование этой общей идеи в эффективную структуру данных — нетривиальная задача. Во-первых, необходимо уметь вычислять монотонную цепь, которая разделяет разбиение на две половины примерно одинакового размера. Во-вторых, поскольку некоторые ребра могут принадлежать нескольким монотонным цепям, необходимо соблюдать осторожность, чтобы гарантировать, что пространство хранения составляет O(n). В-третьих, проверка, находится ли точка слева или справа от монотонного разбиения, занимает время O(n) при наивном подходе. Подробное описание решения первых двух задач выходит за рамки данной статьи. Мы кратко упомянем, как решить третью задачу. Используя двоичный поиск, можно проверить, находится ли точка слева или справа от монотонной цепи за время O(log n). Поскольку для фактического определения местоположения точки необходимо выполнить еще один вложенный двоичный поиск по O(log n) цепям, время запроса составляет O(log² n). Для достижения времени запроса O(log n) необходимо использовать дробную каскадную структуру, поддерживая указатели между ребрами различных монотонных цепей.

Усовершенствование триангуляции

Многоугольник с m вершинами можно разбить на m–2 треугольника. Это можно доказать индукцией, начиная с треугольника. Существует множество алгоритмов для эффективной триангуляции многоугольника, самый быстрый из которых имеет сложность O(n) в наихудшем случае. Следовательно, мы можем разложить каждый многоугольник нашей разбивки на треугольники и ограничить нашу структуру данных случаем разбивок, состоящих исключительно из треугольников. Киркпатрик предложил структуру данных для поиска точки в триангулированных разбиениях, требующую O(n) объема памяти и O(log n) времени запроса. Основная идея заключается в построении иерархии треугольников. Для выполнения запроса мы начинаем с поиска треугольника верхнего уровня, содержащего точку запроса. Поскольку количество треугольников верхнего уровня ограничено константой, эта операция может быть выполнена за O(1) времени. Каждый треугольник имеет указатели на треугольники, с которыми он пересекается на следующем уровне иерархии, и количество этих указателей также ограничено константой. Мы продолжаем поиск, определяя, какой треугольник содержит точку запроса, уровень за уровнем. Структура данных строится в обратном порядке, то есть снизу вверх. Мы начинаем с триангулированной разбивки и выбираем независимое множество вершин для удаления. После удаления вершин мы перестраиваем триангуляцию разбивки. Поскольку разбивка состоит из треугольников, жадный алгоритм может найти независимое множество, содержащее постоянную долю вершин. Следовательно, количество шагов удаления составляет O(log n).

Трапециевидный распад

Рандомизированный подход к этой проблеме основан на трапециевидном разложении, или трапециевидной карте. Трапециевидное разложение получается путем проведения вертикальных лучей, направленных вверх и вниз, из каждой вершины исходного разбиения. Лучи останавливаются, когда достигают ребра, и формируют новое ребро в разбиении. Таким образом, мы получаем подмножество разбиения на полуплоскости, содержащее только O(n) ребер и вершин, поскольку для каждой вершины в исходном разбиении добавляются только две новые вершины и увеличивается количество ребер на четыре. Трапециевидное разложение может быть построено путем добавления сегментов из исходного разбиения по одному, в случайном порядке. Изначально (до добавления каких-либо сегментов) трапециевидное разложение состоит из единственной трапеции – ограничивающего прямоугольника разбиения. Каждый последующий шаг использует запрос на определение местоположения точки для нахождения одной конечной точки следующего отрезка внутри текущего трапециевидного разложения, а затем переходит от полученной трапеции к соседним трапециям, содержащим тот же отрезок, подразделяя и перекомбинируя их для формирования уточненного разложения. Обратный анализ, типичный метод анализа для рандомизированных инкрементальных геометрических алгоритмов, показывает, что ожидаемое количество трапеций, создаваемых при каждой вставке, ограничено константой, а значит общее число шагов алгоритма, не считая запросов на определение местоположения точки, является линейным. Определение местоположения точек в текущем разбиении, выполняемое в рамках этого алгоритма, может быть реализовано с использованием той же структуры, которая в конце алгоритма может быть использована для запросов на определение местоположения точки в конечном трапециевидном разложении. Эта структура данных для определения местоположения точек представляет собой ориентированный ациклический граф, где вершины – это трапеции, существовавшие на каком-то этапе уточнения, а ориентированные ребра соединяют каждую трапецию, которая больше не входит в уточненное разложение, с трапециями, которые её заменили. Запрос на определение местоположения точки выполняется путем прохождения по пути в этом графе, начиная с начальной трапеции, и на каждом шаге выбирается заменяющая трапеция, содержащая точку запроса, до тех пор, пока не будет достигнута трапеция, которая не была заменена. Ожидаемая глубина поиска в этом диграфе, начиная с любой точки запроса, составляет O(log n). Объем памяти, необходимый для структуры данных, пропорционален количеству трапеций, созданных в процессе уточнения, которое в среднем составляет O(n).

Более высокие размеры

Не существует известных общих структур данных для определения местоположения точек с линейным объемом памяти и логарифмическим временем запроса для размерностей больше 2. Поэтому необходимо либо пожертвовать временем запроса, либо объемом памяти, либо ограничиться менее общим типом разбиения. В трехмерном пространстве можно отвечать на запросы о местоположении точки за O(log² n) времени, используя O(n log n) памяти. Основная идея заключается в поддержании нескольких планарных структур данных для определения местоположения точек, соответствующих пересечению разбиения с n параллельными плоскостями, содержащими каждую вершину разбиения. Наивное использование этой идеи привело бы к увеличению объема памяти до O(n²). Подобно разложению на слои, сходство между последовательными структурами данных можно использовать для уменьшения объема памяти до O(n log n), но время запроса при этом увеличивается до O(log² n). В d-мерном пространстве определение местоположения точки можно решить путем рекурсивного проецирования граней в (d-1)-мерное пространство. Хотя время запроса составляет O(log n), объем памяти может быть очень большим. Высокая сложность d-мерных структур данных привела к изучению специальных типов разбиений. Важным примером является случай расположения гиперплоскостей. Расположение n гиперплоскостей определяет O(nd) ячеек, но определение местоположения точки может быть выполнено за O(log n) времени с использованием O(nd) памяти с помощью иерархических разрезов Шазеля. Другой особый тип разбиения называется прямоугольным (или ортогональным) разбиением. В прямоугольном разбиении все ребра параллельны одной из d ортогональных осей. В этом случае определение местоположения точки может быть выполнено за O(logᵈ⁻¹ n) времени с использованием O(n) памяти.