Проблема меры Клиз - Klees measure problem

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

• Приближение выпуклого объема, эффективный алгоритм для выпуклые тела

Ссылки и дополнительная литература

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

• Клее, Виктор (1977), "Может ли мера ${\displaystyle \cup [a_{i},b_{i}]}$ быть вычисленным менее чем ${\displaystyle O(n\log n)}$ шаги? ", Американский математический ежемесячный журнал, 84 (4): 284–285, Дои:10.2307/2318871, JSTOR  2318871, МИСТЕР  0436661.
• Бентли, Джон Л. (1977), Алгоритмы решения прямоугольных задач Кли, Неопубликованные заметки, Департамент компьютерных наук, Университет Карнеги-Меллона.
• Фредман, Майкл Л.; Вайде, Брюс (1978), "Сложность вычисления меры ${\displaystyle \cup [a_{i},b_{i}]}$", Коммуникации ACM, 21 (7): 540–544, Дои:10.1145/359545.359553, МИСТЕР  0495193, S2CID  16493364.
• ван Леувен, Ян; Вуд, Дерик (1981), "Проблема меры для прямоугольных диапазонов в d-Космос", Журнал алгоритмов, 2 (3): 282–300, Дои:10.1016/0196-6774(81)90027-4, HDL:1874/15897, МИСТЕР  0632450.
• Овермарс, Марк Х.; Яп, Чи-Кенг (1991), "Новые верхние оценки в проблеме меры Кли", SIAM Журнал по вычислениям, 20 (6): 1034–1045, Дои:10.1137/0220065, HDL:1874/16614, МИСТЕР  1135747.
• Хлебус, Богдан С. (1998), "О проблеме меры Кли в малых размерностях", Материалы 25-й конференции «Современные тенденции в теории и практике информатики» (СОФСЕМ-98), Конспект лекций по информатике, 1521, Берлин: Springer-Verlag, стр.304–311, Дои: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, Дои:10.1109 / FOCS.2013.51, ISBN  978-0-7695-5135-7, S2CID  11648588.

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

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

Рекомендации

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