El problema de medición de Klee

En geometría computacional , el problema de la medida de Klee es el problema de determinar cuán eficientemente se puede calcular la medida de una unión de rangos rectangulares ( multidimensionales ). Aquí, un rango rectangular d -dimensional se define como un producto cartesiano de d intervalos de números reales , que es un subconjunto de R ^d .

El problema recibe su nombre de Victor Klee , quien propuso un algoritmo para calcular la longitud de la unión de intervalos (el caso d = 1), el cual posteriormente demostró ser óptimamente eficiente en el sentido de la teoría de la complejidad computacional . La complejidad computacional para calcular el área de la unión de rangos rectangulares bidimensionales también se conoce actualmente, pero el caso d ≥ 3 sigue siendo un problema abierto .

En 1977, Victor Klee consideró el siguiente problema: dada una colección de n intervalos en la recta real , calcular la longitud de su unión. Luego presentó un algoritmo para resolver este problema con complejidad computacional (o "tiempo de ejecución").${\displaystyle O(n\log n)}$— Véase la notación Big O para comprender el significado de esta afirmación. Este algoritmo, basado en la ordenación de los intervalos, fue posteriormente demostrado como óptimo por Michael Fredman y Bruce Weide (1978).

Más tarde, en 1977, Jon Bentley consideró un análogo bidimensional de este problema: dada una colección de n rectángulos , hallar el área de su unión. También obtuvo una complejidad${\displaystyle O(n\log n)}$El algoritmo, ahora conocido como algoritmo de Bentley , se basa en reducir el problema a n problemas unidimensionales : esto se logra trazando una línea vertical sobre el área. Mediante este método, se puede calcular el área de la unión sin construirla explícitamente. El algoritmo de Bentley también es óptimo (en el caso bidimensional) y se utiliza en gráficos por computadora , entre otras áreas.

Estos dos problemas son los casos unidimensional y bidimensional de una cuestión más general: dada una colección de rangos rectangulares n- dimensionales , calcular la medida de su unión. Este problema general es el problema de la medida de Klee.

Cuando se generaliza al caso d -dimensional, el algoritmo de Bentley tiene un tiempo de ejecución de${\displaystyle O(n^{d-1}\log n)}$Esto resulta no ser óptimo, porque solo descompone el problema d- dimensional en problemas n ( d-1 )-dimensionales, y no descompone aún más esos subproblemas. En 1981, Jan van Leeuwen y Derek Wood mejoraron el tiempo de ejecución de este algoritmo a${\displaystyle O(n^{d-1})}$para d ≥ 3 mediante el uso de quadtrees dinámicos .

En 1988, Mark Overmars y Chee Yap propusieron un${\displaystyle O(n^{d/2}\log n)}$algoritmo para d ≥ 3. Su algoritmo utiliza una estructura de datos particular similar a un árbol kd para descomponer el problema en componentes bidimensionales y agregarlos de manera eficiente; los problemas bidimensionales se resuelven eficientemente mediante una estructura de enrejado . Aunque asintóticamente más rápido que el algoritmo de Bentley, sus estructuras de datos utilizan mucho más espacio, por lo que solo se utiliza en problemas donde n o d son grandes. En 1998, Bogdan Chlebus propuso un algoritmo más simple con el mismo tiempo de ejecución asintótico para los casos especiales comunes donde d es 3 o 4.

En 2013, Timothy M. Chan desarrolló un algoritmo más simple que evita la necesidad de estructuras de datos dinámicas y elimina el factor logarítmico, reduciendo el mejor tiempo de ejecución conocido para d ≥ 3 a${\displaystyle O(n^{d/2})}$.

El único límite inferior conocido para cualquier d es${\displaystyle \Omega (n\log n)}$y se conocen algoritmos óptimos con este tiempo de ejecución para d =1 y d =2. El algoritmo de Chan proporciona una cota superior de${\displaystyle O(n^{d/2})}$Para d ≥ 3, queda por determinar si existen algoritmos más rápidos o si se pueden demostrar cotas inferiores más ajustadas. En particular, se desconoce si el tiempo de ejecución del algoritmo depende de d . Además, se plantea la cuestión de si existen algoritmos más rápidos que puedan manejar casos especiales (por ejemplo, cuando las coordenadas de entrada son números enteros dentro de un rango acotado).

El problema de la medida de Klee unidimensional (unión de intervalos) se puede resolver en${\displaystyle O(n\log p)}$donde p denota el número de puntos de perforación necesarios para atravesar todos los intervalos ^{[ 1 ]} (la unión de intervalos atravesados ​​por un punto común se puede calcular en tiempo lineal calculando los extremos). El parámetro p es un parámetro adaptativo que depende de la configuración de entrada, y el algoritmo de perforación ^{[ 2 ]} produce un algoritmo adaptativo para el problema de la medida de Klee.

• Aproximación de volumen convexo , un algoritmo eficiente para cuerpos convexos.