Задача Клее о мере объединения прямоугольных областей
Klee's measure problem
Проблема Клея в вычислительной геометрии: эффективное вычисление меры объединения прямоугольных областей. Сложность растет с размерностью, решение для d≥3 – открытый вопрос.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Проблема вычислительной геометрии
Computational geometry problem
В вычислительной геометрии проблема измерения Кли (Klee's measure problem) заключается в определении эффективности вычисления меры объединения (многомерных) прямоугольных областей. Здесь d-мерная прямоугольная область определяется как декартово произведение d интервалов действительных чисел, являющееся подмножеством Rd. Проблема названа в честь Виктора Кли, который предложил алгоритм для вычисления длины объединения интервалов (случай d = 1), который впоследствии был признан оптимально эффективным с точки зрения теории вычислительной сложности. Вычислительная сложность определения площади объединения 2-мерных прямоугольных областей также известна, однако случай d ≥ 3 остаётся нерешённой проблемой.
In computational geometry, Klee's measure problem is the problem of determining how efficiently the measure of a union of (multidimensional) rectangular ranges can be computed. Here, a d dimensional rectangular range is defined to be a Cartesian product of d intervals of real numbers, which is a subset of Rd. The problem is named after Victor Klee, who gave an algorithm for computing the length of a union of intervals (the case d = 1) which was later shown to be optimally efficient in the sense of computational complexity theory. The computational complexity of computing the area of a union of 2 dimensional rectangular ranges is now also known, but the case d ≥ 3 remains an open problem.
История и алгоритмы
В 1977 году Виктор Кли рассмотрел следующую задачу: для заданного набора из n интервалов на вещественной прямой вычислить длину их объединения. Затем он представил алгоритм для решения этой задачи с вычислительной сложностью (или "временем работы") — см. нотацию «Большое О» для понимания этого утверждения. Этот алгоритм, основанный на сортировке интервалов, позднее был доказан оптимальным Майклом Фредманом и Брюсом Вайдом (1978). В конце 1977 года Джон Бентли рассмотрел двумерный аналог этой задачи: для заданного набора из n прямоугольников найти площадь их объединения. Он также разработал алгоритм с определенной сложностью, ныне известный как алгоритм Бентли, основанный на сведении задачи к n одномерным задачам: это достигается путем сканирования области вертикальной линией. С помощью этого метода площадь объединения может быть вычислена без явного построения самого объединения. Алгоритм Бентли также известен как оптимальный (в двумерном случае) и используется, в частности, в компьютерной графике. Эти две задачи являются одномерным и двумерным случаями более общей постановки: для заданного набора из n d-мерных прямоугольных областей вычислить меру их объединения. Эта общая задача известна как задача измерения Кли. При обобщении на d-мерный случай время работы алгоритма Бентли составляет , что оказывается неоптимальным, поскольку он лишь разлагает d-мерную задачу на n (d-1)-мерные подзадачи, не осуществляя дальнейшего их разложения. В 1981 году Ян ван Леувен и Дерек Вуд улучшили время работы этого алгоритма до для d ≥ 3, используя динамические четверенки. В 1988 году Марк Овермарс и Чи Яп предложили алгоритм со сложностью для d ≥ 3. Их алгоритм использует специальную структуру данных, подобную kd-дереву, для разложения задачи на двумерные компоненты и эффективной агрегации этих компонентов; сами двумерные задачи эффективно решаются с использованием треллис-структуры. Хотя асимптотически более быстрый, чем алгоритм Бентли, он требует значительно больше памяти для хранения структур данных, поэтому применяется только к задачам, где n или d велики. В 1998 году Богдан Члебус предложил более простой алгоритм с тем же асимптотическим временем работы для распространенных частных случаев, когда d равно 3 или 4. В 2013 году Тимоти М. Чан разработал более простой алгоритм, который не требует динамических структур данных и устраняет логарифмический фактор, снижая наилучшее известное время работы для d ≥ 3 до .
In 1977, Victor Klee considered the following problem: given a collection of n intervals in the real line, compute the length of their union. He then presented an algorithm to solve this problem with computational complexity (or "running time") — see Big O notation for the meaning of this statement. This algorithm, based on sorting the intervals, was later shown by Michael Fredman and Bruce Weide (1978) to be optimal. Later in 1977, Jon Bentley considered a 2 dimensional analogue of this problem: given a collection of n rectangles, find the area of their union. He also obtained a complexity algorithm, now known as Bentley's algorithm, based on reducing the problem to n 1 dimensional problems: this is done by sweeping a vertical line across the area. Using this method, the area of the union can be computed without explicitly constructing the union itself. Bentley's algorithm is now also known to be optimal (in the 2 dimensional case), and is used in computer graphics, among other areas. These two problems are the 1 and 2 dimensional cases of a more general question: given a collection of n d dimensional rectangular ranges, compute the measure of their union. This general problem is Klee's measure problem. When generalized to the d dimensional case, Bentley's algorithm has a running time of This turns out not to be optimal, because it only decomposes the d dimensional problem into n (d 1) dimensional problems, and does not further decompose those subproblems. In 1981, Jan van Leeuwen and Derek Wood improved the running time of this algorithm to for d ≥ 3 by using dynamic quadtrees. In 1988, Mark Overmars and Chee Yap proposed an algorithm for d ≥ 3. Their algorithm uses a particular data structure similar to a kd tree to decompose the problem into 2 dimensional components and aggregate those components efficiently; the 2 dimensional problems themselves are solved efficiently using a trellis structure. Although asymptotically faster than Bentley's algorithm, its data structures use significantly more space, so it is only used in problems where either n or d is large. In 1998, Bogdan Chlebus proposed a simpler algorithm with the same asymptotic running time for the common special cases where d is 3 or 4. In 2013, Timothy M. Chan developed a simpler algorithm that avoids the need for dynamic data structures and eliminates the logarithmic factor, lowering the best known running time for d ≥ 3 to .
Известные границы
Единственная известная нижняя граница для любого d – , и оптимальные алгоритмы с таким временем работы известны для d=1 и d=2. Алгоритм Чана предоставляет верхнюю границу для d ≥ 3, поэтому для d ≥ 3 остаётся открытым вопрос о том, существуют ли более быстрые алгоритмы, или, альтернативно, можно ли доказать более строгие нижние границы. В частности, остаётся нерешённым вопрос, должно ли время работы алгоритма зависеть от d. Кроме того, остаётся открытым вопрос о существовании более быстрых алгоритмов, способных обрабатывать частные случаи (например, когда входные координаты – целые числа в ограниченном диапазоне). Одномерная задача измерения Кли (объединение интервалов) может быть решена за , где p обозначает число точек прокола, необходимых для протыкания всех интервалов (объединение интервалов, проткнутых общей точкой, может быть вычислено за линейное время путём вычисления экстремумов). Параметр p является адаптивным параметром, зависящим от входной конфигурации, а алгоритм протыкания даёт адаптивный алгоритм для задачи измерения Кли.
The only known lower bound for any d is , and optimal algorithms with this running time are known for d=1 and d=2. The Chan algorithm provides an upper bound of for d ≥ 3, so for d ≥ 3, it remains an open question whether faster algorithms are possible, or alternatively whether tighter lower bounds can be proven. In particular, it remains open whether the algorithm's running time must depend on d. In addition, the question of whether there are faster algorithms that can deal with special cases (for example, when the input coordinates are integers within a bounded range) remains open. The 1D Klee's measure problem (union of intervals) can be solved in where p denotes the number of piercing points required to stab all intervals (the union of intervals pierced by a common point can be calculated in linear time by computing the extrema). Parameter p is an adaptive parameter that depends on the input configuration, and the piercing algorithm yields an adaptive algorithm for Klee's measure problem.
Важные документы
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Вторичная литература
Франко П. Препарата и Майкл И. Шамос (1985). Вычислительная геометрия (Springer Verlag, Берлин). Проблема измерения Кли из списка нерешенных задач профессора Джеффа Эриксона в области вычислительной геометрии. (Проверено 8 ноября 2005 года, последняя редакция от 31 июля 1998 года.)
Franco P. Preparata and Michael I. Shamos (1985). Computational Geometry (Springer Verlag, Berlin). Klee's Measure Problem, from Professor Jeff Erickson's list of open problems in computational geometry. (Accessed November 8, 2005, when the last update was July 31, 1998.)