WikiDer > Кинетическая выпуклая оболочка

Kinetic convex hull

А кинетическая выпуклая оболочка структура данных - это кинетическая структура данных который поддерживает выпуклая оболочка набора непрерывно движущихся точек.[1] Его следует отличать от динамическая выпуклая оболочка структуры данных, которые обрабатывают точки, претерпевающие дискретные изменения, такие как вставки или удаления точек, а не непрерывное движение.

2D случай

Самая известная структура данных для двумерной кинетической задачи выпуклой оболочки принадлежит Basch, Гибас, и Хершбергер. Эта структура данных отзывчивый, эффективный, компактный и местный.[1]

Структура данных

В двойной выпуклой оболочки множества точек - это верхняя и нижняя оболочки двойственного множества прямых. Следовательно, поддержание верхней и нижней оболочки набора движущихся линий эквивалентно поддержанию выпуклой оболочки набора движущихся точек. Вычисление верхней и нижней огибающих - эквивалентные задачи, поэтому вычисление верхней оболочки набора линий эквивалентно вычислению выпуклой оболочки набора движущихся точек. Верхняя оболочка набора статических линий может быть вычислена с помощью разделяй и властвуй алгоритм который разбивает строки на два набора равного размера, рекурсивно вызывает себя для двух наборов, чтобы найти их верхние конверты, а затем объединяет два результирующих верхних конверта. Шаг слияния выполняется с использованием развертка вертикальной линии. Назовите первый набор точек синим, а второй набор точек - красным.

Стандартный алгоритм линейной развертки для объединения верхних огибающих проходит через все вершины красного и синего верхних огибающих слева направо. Последние обнаруженные красные и синие точки сохраняются по мере прохождения линии. При обнаружении точки алгоритм проверяет, находится ли точка выше или ниже сегмента, следующего за последней встреченной точкой противоположного цвета. Если он выше, эта точка добавляется к объединенному верхнему конверту. Если он другого цвета, чем последняя добавленная точка, красный и синий конверты пересеклись, поэтому точка пересечения также добавляется к объединенному верхнему конверту.[2]

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

  • х-сертификаты () используются для удостоверения порядка вершин красного и синего конвертов. Это сертификаты на кинетический отсортированный список на множестве вершин. Поскольку каждый балл включает 2 строки, а сертификат включает 2 балла, каждый сертификат включает 4 строки.
  • y-сертификаты () используются для подтверждения того, что вершина находится выше или ниже ребра. Сертификаты появляются для всех сравнений, которые происходят во время алгоритма.

Пока все эти сертификаты сохраняются, шаги слияния будут выполняться одинаково, поэтому конечный верхний конверт будет таким же. Кинетическая структура данных для верхних огибающих может быть создана с помощью этих сертификатов для сертификации алгоритма статического верхнего конверта. Однако эта схема не является локальной, потому что одна линия будет задействована во многих y-сертификатах, если она остается наверху или внизу по мере того, как встречается много точек из другого конверта.

Таким образом, необходимо ввести s-сертификаты (), который удостоверяет, что наклон одной линии больше или меньше наклона другой линии.

Для сертификации последовательности ребер и вершин, полученных в результате слияния, достаточно иметь следующие сертификаты для всех точек ab, имея только O (1) сертификатов на строку:[1]

Изображение сертификатов в нескольких разных случаях
Сертификаты удостоверяют структуру пересечения красного и синего конвертов путем подтверждения пересечений (вверху слева) или отсутствия пересечений (вверху справа и внизу). Стрелки указывают, какие элементы сравниваются сертификатом.
  1. : . обозначает ближайшую к справа. Этот сертификат хранится для всех точек которые имеют другой цвет, чем острие, , который следует за ними.
  2. : или . Этот сертификат хранится для всех точек такой, что пересекает . обозначает конкурентное преимущество , край другого конверта, находящийся выше или ниже .
  3. : или . Этот сертификат хранится для всех точек такой, что пересекает .
  4. : . Этот сертификат хранится для всех точек для которого и .
  5. : . Этот сертификат хранится для всех точек для которого и .
  6. : . Этот сертификат хранится для всех точек для которого и .
  7. : . Этот сертификат хранится для всех точек для которого и .
  8. : . Этот сертификат хранится для всех точек для которого и .

Первый сертификат, , удостоверяет x-порядок точек в красном и синем конвертах. Второй и третий сертификаты, и , удостоверяем пересечения красного и синего конвертов. Остальные 5 сертификатов, , , , , и расположите края, не входящие в верхние конверты, в последовательности уклонов краев, находящихся над ним. Если наклон находится в начале или в конце последовательности, или удостоверяю это. Если он находится в середине последовательности , и удостоверяю это, и удостоверяет, что точка пересечения двух линий, между которыми находится наклон кромки, находится над ней. Этих одного или трех сертификатов достаточно, чтобы доказать, что все ребра находятся выше этой линии. В отличие от предыдущей схемы все строки задействованы только в постоянном количестве сертификатов. В случае сбоя этих сертификатов объединенный конверт и сертификаты могут быть обновлены за O (1) раз.

Кинетическая структура данных для выпуклой оболочки построена с использованием этих сертификатов для сертификации рекурсивного слияния верхних конвертов. Когда сертификаты терпят неудачу, их слияние обновляется, и если конверт, полученный в результате слияния, изменяется, изменения распространяются вверх по всем слияниям, которые зависят от результата слияния.[1]

Спектакль

Эта структура данных отзывчивый, местный, компактный, и эффективный. Это связано с логарифмической глубиной слияния, используемой для сертификации верхнего конверта.[1]

  • Отзывчивый: Когда сертификат не работает, требуется O (1), чтобы исправить слияние, которое он удостоверяет. Если результирующий конверт изменится, это изменение должно распространиться на все слияния, которые зависят от результата измененного слияния. Есть O (журнал п) таких слияний, поэтому обновление может быть выполнено за O (журнал п) общее время.
  • Местный: Каждая строка занимает максимум O (журнал п) сертификаты. Это потому, что каждая строка участвует в постоянном количестве сертификатов при каждом слиянии, а каждая строка находится в O (журнал п) общее количество слияний.
  • Компактность: Максимальное количество сертификатов, используемых в этой структуре данных, составляет O (п журнал п). Это связано с тем, что каждое слияние включает количество сертификатов, линейное по количеству слитых строк. Заверение верхнего конверта п строк требует сертификатов для верхнего конверта слияния двух подмножеств п/ 2 строки, и сертификаты на объединение конвертов. Таким образом, количество сертификатов C (п), необходимого для заверения верхнего конверта п прямых удовлетворяет рекуррентности C (п) = 2C (п/ 2) + O (п), где C (1) = O (1). Посредством основная теорема для повторений "разделяй и властвуй", C (п) = O (п журнал п).
  • Эффективность: Максимальное количество событий, обрабатываемых этим алгоритмом на алгебраический или псевдоалгебраический траектории близки к квадратичным, для всех .[3][4] Выпуклые оболочки линейно движущихся точек могут изменяться раз.[5] Таким образом, эта структура данных эффективна.

Высшие измерения

Нахождение эффективный Кинетическая структура данных для поддержания выпуклой оболочки движущихся точек с размерами больше 2 является открытой проблемой.[1]

Связанные проблемы

Кинетическая выпуклая оболочка может использоваться для решения следующих связанных задач:[6]

использованная литература

  1. ^ а б c d е ж Баш, Жюльен; Guibas, Leonidas J .; Хершбергер, Джон (апрель 1999 г.). «Структуры данных для мобильных данных» (PDF). J. Алгоритмы. 31 (1): 1–28. CiteSeerX 10.1.1.134.6921. Дои:10.1006 / jagm.1998.0988.
  2. ^ Хершбергер, Джон (21 декабря 1989 г.). "Нахождение верхнего конверта п отрезки в O (п журнал п) время ». Письма об обработке информации. 33 (4): 169–174. Дои:10.1016/0020-0190(89)90136-1.
  3. ^ Agarwal, Pankaj K .; Шварцкопф, Отфрид; Шарир, Миха (январь 1996). «Накладка нижних конвертов и ее приложения». Дискретная и вычислительная геометрия. 15 (1): 1–13. CiteSeerX 10.1.1.54.5488. Дои:10.1007 / BF02716576.
  4. ^ Шарир, Миха (1994). «Почти жесткие верхние границы для нижних огибающих в более высоких измерениях. Дискретная и вычислительная геометрия». Дискретная и вычислительная геометрия. 12 (1): 327–345. Дои:10.1007 / BF02574384.
  5. ^ Agarwal, Pankaj K .; Guibas, Leonidas J .; Хершбергер, Джон; Вич, Эрик (январь 2001 г.). «Сохранение протяженности набора движущихся точек». Дискретная и вычислительная геометрия. 26 (3): 353–374. CiteSeerX 10.1.1.47.8510. Дои:10.1007 / s00454-001-0019-х.
  6. ^ Agarwal, Pankaj K .; Guibas, Leonidas J .; Хершбергер, Джон; Вич, Эрик (август 1997). «Сохранение протяженности набора движущихся точек». Конспект лекций по информатике, том 1272. 5-й семинар по алгоритмам и структурам данных (WADS '97). С. 31–44. Дои:10.1007/3-540-63307-3_46.