Проблема меры Клее

В вычислительной геометрии проблема меры Кли — это проблема определения того, насколько эффективно меру объединения можно ( многомерных вычислить ) прямоугольных диапазонов. Здесь d -мерный прямоугольный диапазон определяется как произведение d R интервалов действительных чисел , которое подмножеством является декартово ^д.

Проблема названа в честь Виктора Клее , который дал алгоритм вычисления длины объединения интервалов (случай d = 1), который, как позже было показано, является оптимально эффективным с точки зрения теории сложности вычислений . Вычислительная сложность вычисления площади объединения двумерных прямоугольных диапазонов теперь также известна, но случай d ≥ 3 остаётся открытой проблемой .

История и алгоритмы

В 1977 году Виктор Клее рассмотрел следующую задачу: по набору из n интервалов вещественной прямой вычислить длину их объединения. Затем он представил алгоритм решения этой проблемы с вычислительной сложностью (или «временем выполнения»). $O(n\log n)$ - см. обозначение Big O, чтобы узнать значение этого утверждения. Этот алгоритм, основанный на сортировке интервалов, позже был показан Майклом Фредманом и Брюсом Вейде (1978) как оптимальный.

Позже, в 1977 году, Джон Бентли рассмотрел двумерный аналог этой задачи: по набору из n прямоугольников найти площадь их объединения. Он также получил сложность $O(n\log n)$ Алгоритм, ныне известный как алгоритм Бентли , основан на сведении задачи к n 1 -мерным задачам: это делается путем проведения вертикальной линии по площади. Используя этот метод, площадь объединения можно вычислить без явного построения самого объединения. Теперь известно, что алгоритм Бентли является оптимальным (в двумерном случае) и используется в компьютерной графике , среди других областей, .

Эти две задачи являются одномерными и двумерными случаями более общего вопроса: по набору n d -мерных прямоугольных диапазонов вычислить меру их объединения. Эта общая проблема — проблема меры Клее.

При обобщении на d -мерный случай время работы алгоритма Бентли составляет $O(n^{d-1}\log n)$ . Это оказывается неоптимальным , поскольку оно только разлагает d -мерную задачу на n ( d-1 )-мерные задачи и не разлагает дальше эти подзадачи. В 1981 году Ян ван Леувен и Дерек Вуд улучшили время работы этого алгоритма до $O(n^{d-1})$ для d ≥ 3 с использованием динамических квадродеревьев .

В 1988 году Марк Овермарс и Чи Яп предложили $O(n^{d/2}\log n)$ алгоритм для d ≥ 3. Их алгоритм использует особую структуру данных, похожую на kd-дерево, для разложения проблемы на двумерные компоненты и эффективного агрегирования этих компонентов; сами двумерные задачи эффективно решаются с использованием решетчатой структуры. Хотя он асимптотически быстрее алгоритма Бентли, его структуры данных используют значительно больше места, поэтому он используется только в задачах, где либо n , либо d велики. В 1998 году Богдан Хлебус предложил более простой алгоритм с тем же асимптотическим временем работы для общих особых случаев, когда d равно 3 или 4.

В 2013 году Тимоти М. Чен разработал более простой алгоритм, который позволяет избежать необходимости в динамических структурах данных и исключает логарифмический коэффициент, снижая лучшее известное время работы для d ≥ 3 до $O(n^{d/2})$ .

Известные границы

Единственная известная нижняя граница для любого d — это $\Omega (n\log n)$ , и оптимальные алгоритмы с таким временем работы известны для d =1 и d =2. Алгоритм Чана дает верхнюю границу $O(n^{d/2})$ для d ≥ 3, поэтому для d ≥ 3 остается открытым вопрос, возможны ли более быстрые алгоритмы или, альтернативно, можно ли доказать более точные нижние оценки. В частности, остается открытым вопрос о том, должно ли время работы алгоритма зависеть от d . Кроме того, остается открытым вопрос о том, существуют ли более быстрые алгоритмы, способные справиться с особыми случаями (например, когда входные координаты являются целыми числами в ограниченном диапазоне).

Одномерную проблему меры Кли (объединение интервалов) можно решить в $O(n\log p)$ где p обозначает количество точек прокалывания, необходимых для прокалывания всех интервалов ^{[ 1 ]} (объединение интервалов, пронзенных общей точкой, можно вычислить за линейное время путем вычисления экстремумов). Параметр p — адаптивный параметр, зависящий от входной конфигурации и алгоритма прошивки. ^{[ 2 ]} дает адаптивный алгоритм для задачи меры Кли.

См. также

Аппроксимация выпуклого объема , эффективный алгоритм для выпуклых тел

Ссылки и дальнейшее чтение

Важные документы

Клее, Виктор (1977), "Может ли мера $\cup [a_{i},b_{i}]$ быть вычислено менее чем за $O(n\log n)$ шаги?», American Mathematical Monthly , 84 (4): 284–285, doi : 10.2307/2318871 , JSTOR 2318871 , MR 0436661 .
Бентли, Джон Л. (1977), Алгоритмы для задач прямоугольника Кли , Неопубликованные заметки, Факультет компьютерных наук, Университет Карнеги-Меллона .
Фредман, Майкл Л .; Вейде, Брюс (1978), «Сложность вычисления меры $\cup [a_{i},b_{i}]$ », « Сообщения ACM» , 21 (7): 540–544, doi : 10.1145/359545.359553 , MR 0495193 , S2CID 16493364 .
ван Леувен, Ян ; Вуд, Дерик (1981), «Проблема меры для прямоугольных диапазонов в d -пространстве», Journal of Algorithms , 2 (3): 282–300, doi : 10.1016/0196-6774(81)90027-4 , hdl : 1874 /15897 , МР 0632450 .
Овермарс, Марк Х .; Яп, Чи-Кенг (1991), «Новые верхние границы в задаче о мере Кли», SIAM Journal on Computing , 20 (6): 1034–1045, doi : 10.1137/0220065 , hdl : 1874/16614 , MR 1135747 .
Хлебус, Богдан С. (1998), «О проблеме меры Клее в малых размерностях», Материалы 25-й конференции по современным тенденциям в теории и практике информатики (SOFSEM-98) , Конспекты лекций по информатике , том. 1521, Берлин: Springer-Verlag, стр. 304–311 , doi : 10.1007/3-540-49477-4_22 , ISBN. 978-3-540-65260-1 .
Чан, Тимоти М. (2013), «Проблема меры Кли стала проще», Труды 54-го симпозиума IEEE по основам компьютерных наук (FOCS) (PDF) , стр. 410–419, CiteSeerX 10.1.1.643.26 , doi : 10.1109/FOCS.2013.51 , ISBN 978-0-7695-5135-7 , S2CID 11648588 .

Вторичная литература

Франко П. Препарата и Майкл И. Шамос (1985). Вычислительная геометрия (Springer-Verlag, Берлин).
Проблема меры Клее профессора Джеффа Эриксона из списка открытых проблем вычислительной геометрии . (По состоянию на 8 ноября 2005 г., последнее обновление было 31 июля 1998 г.)

Ссылки

^ «Адаптивная вычислительная геометрия», Ф. Нильсен, PDF
^ «Быстрая резка коробок больших размеров», Ф. Нильсен, Теоретическая информатика Том 246, выпуски 1–2, 6 сентября 2000 г., страницы 53–72. PDF

[1] «Адаптивная вычислительная геометрия», Ф. Нильсен, PDF

[2] «Быстрая резка коробок больших размеров», Ф. Нильсен, Теоретическая информатика Том 246, выпуски 1–2, 6 сентября 2000 г., страницы 53–72. PDF

[ 1 ]

[ 2 ]