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

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

2D-случай

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

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

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

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

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

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

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

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

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

Изображение сертификатов в нескольких разных случаях — Сертификаты удостоверяют структуру пересечения красного и синего конвертов путем подтверждения пересечений (вверху слева) или отсутствия пересечений (вверху справа и внизу). Стрелки указывают, какие элементы сравниваются по сертификату.

$x[ab]$ : $ab<_{x}ab.next$ . $ab.next$ обозначает вершину, ближайшую к $ab$ справа. Этот сертификат сохраняется для всех точек $ab$ которые имеют цвет, отличный от точки, $ab.next$ , который следует за ними.
$yli[ab]$ : $ab<_{y}ce(ab)$ или $ab>_{y}ce(ab)$ . Этот сертификат сохраняется для всех точек $ab$ такой, что $b$ пересекает $ce(ab)$ . $ce(ab)$ обозначает преимущество соперника $ab$ , край другого конверта, который находится выше или ниже $ab$ .
$yri[ab]$ : $ab<_{y}ce(ab)$ или $ab>_{y}ce(ab)$ . Этот сертификат сохраняется для всех точек $ab$ такой, что $a$ пересекает $ce(ab)$ .
$yt[ab]$ : $ce(ab)<_{y}ab$ . Этот сертификат сохраняется для всех точек $ab$ для чего $a<_{s}ce(ab)<_{s}b$ и $ce(ab)<_{y}ab$ .
$srt[ab]$ : $a<_{s}ce(ab)$ . Этот сертификат сохраняется для всех точек $ab$ для чего $a<_{s}ce(ab)<_{s}b$ и $ce(ab)<_{y}ab$ .
$srt[ab]$ : $ce(ab)<_{s}b$ . Этот сертификат сохраняется для всех точек $ab$ для чего $a<_{s}ce(ab)<_{s}b$ и $ce(ab)<_{y}ab$ .
$sl[ab]$ : $b<_{s}ce(ab)$ . Этот сертификат сохраняется для всех точек $ab$ для чего $b<_{s}ce(ab)$ и $ab<_{y}ce(ab)$ .
$sr[ab]$ : $ce(ab)<_{s}a$ . Этот сертификат сохраняется для всех точек $ab$ для чего $ce(ab)<_{s}a$ и $ab<_{y}ce(ab)$ .

Первый сертификат, $x[ab]$ , подтверждает X-упорядочение точек в красных и синих конвертах. Второй и третий сертификаты, $yli[ab]$ и $yri[ab]$ , удостоверьте пересечение красного и синего конвертов. Остальные 5 сертификатов, $yt[ab]$ , $srt[ab]$ , $srt[ab]$ , $sl[ab]$ , и $sr[ab]$ ребра, не попавшие в верхние конверты, расположите в последовательности наклонов ребер, находящихся над ним. Если наклон находится в начале или конце последовательности, $sl$ или $sr$ подтвердить это. Если оно находится в середине последовательности $slt$ , и $srt$ подтвердить это и $yt$ удостоверяет, что точка пересечения двух линий, между которыми находится наклон края, находится над ним. Этих одного-трех сертификатов достаточно, чтобы доказать, что все ребра находятся выше этой линии. В отличие от предыдущей схемы, все линии задействованы только в постоянном количестве сертификатов. В случае сбоя одного из этих сертификатов объединенный конверт и сертификаты могут быть обновлены за время O(1).

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

Производительность

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

Отзывчивость: при сбое сертификата требуется O(1) для исправления слияния, которое он сертифицирует. Если полученный конверт изменится, это изменение должно распространиться на все слияния, которые зависят от результата измененного слияния. Таких слияний существует O(log n ), поэтому обновление может быть выполнено за O(log n ). общее время
Локальный: каждая строка задействована в большинстве сертификатов O(log n ). Это связано с тем, что каждая строка участвует в постоянном количестве сертификатов при каждом слиянии, а общее количество слияний каждой строки составляет O(log n ).
Компактность: максимальное количество сертификатов, используемых в этой структуре данных, равно O( n log n ). Это связано с тем, что каждое слияние включает в себя количество сертификатов, линейно зависящее от количества объединенных строк. Для сертификации верхнего конверта из n строк требуются сертификаты для объединения верхнего конверта двух подмножеств из n /2 строк и сертификаты для объединения конвертов. Таким образом, количество сертификатов C( n ), необходимых для сертификации верхнего конверта из n строк, удовлетворяет повторяемости C( n )=2C( n /2)+O( n ), где C(1)=O(1) . Согласно основной теореме для рекурсий «разделяй и властвуй» , C( n )=O( n log n ).
Эффективность: максимальное количество событий, обрабатываемых этим алгоритмом на алгебраических или псевдоалгебраических траекториях, близко к квадратичному, $O(n^{2+\epsilon })$ для всех $\epsilon >0$ . ^[3]^[4] Выпуклые оболочки линейно движущихся точек могут изменяться. $\Omega (n^{2})$ раз. ^[5] Таким образом, эта структура данных эффективна.

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

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

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

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

Ссылки

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

[BGH99-1] Jump up to: ^а ^б ^с ^д ^и ^ж Баш, Жюльен; Гибас, Леонидас Дж .; Хершбергер, Джон (апрель 1999 г.). «Структуры данных для мобильных данных» (PDF) . Журнал алгоритмов . 31 (1): 1–28. CiteSeerX 10.1.1.134.6921 . дои : 10.1006/jagm.1998.0988 . S2CID 8013433 .

[2] Хершбергер, Джон (21 декабря 1989 г.). «Нахождение верхней огибающей n отрезков линии за время O ( n log n )». Письма об обработке информации . 33 (4): 169–174. дои : 10.1016/0020-0190(89)90136-1 .

[ASS96-3] Агарвал, Панкадж К .; Шварцкопф, Отфрид; Шарир, Миша (январь 1996 г.). «Наложение нижних конвертов и его приложения». Дискретная и вычислительная геометрия . 15 (1): 1–13. CiteSeerX 10.1.1.54.5488 . дои : 10.1007/BF02716576 . S2CID 1261935 .

[Sha94-4] Шарир, Миша (1994). «Почти жесткие верхние границы для нижних конвертов в более высоких измерениях» . Дискретная и вычислительная геометрия . 12 (1): 327–345. дои : 10.1007/BF02574384 .

[AGHV01-5] Агарвал, Панкадж К .; Гибас, Леонидас Дж .; Хершбергер, Джон; Вич, Эрик (январь 2001 г.). «Поддержание размера набора движущихся точек». Дискретная и вычислительная геометрия . 26 (3): 353–374. CiteSeerX 10.1.1.47.8510 . дои : 10.1007/s00454-001-0019-x .

[AGHV97-6] Агарвал, Панкадж К .; Гибас, Леонидас Дж .; Хершбергер, Джон; Вич, Эрик (август 1997 г.). «Сохранение размера набора движущихся точек» . Конспекты лекций по информатике, том 1272 . 5-й семинар по алгоритмам и структурам данных (WADS '97) . стр. 31–44. дои : 10.1007/3-540-63307-3_46 .

[1]

[2]

[3]

[4]

[5]

[6]