Задача о мере Клее

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

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

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

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

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

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

Набор прямоугольных диапазонов («решеток»), площадь которых необходимо измерить.