El problema de la medida de Klee

Problema de geometría computacional

Un conjunto de rangos rectangulares ('enrejados') cuya área debe medirse.

En geometría computacional , el problema de la medida de Klee es el problema de determinar con qué eficiencia 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 dio un algoritmo para calcular la longitud de una unión de intervalos (el caso d = 1) que luego se demostró que era óptimamente eficiente en el sentido de la teoría de la complejidad computacional . Ahora también se conoce la complejidad computacional de calcular el área de una unión de rangos rectangulares bidimensionales, pero el caso d ≥ 3 sigue siendo un problema abierto .

Historia y algoritmos

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") ; consulte la notación Big O para conocer el significado de esta afirmación. Michael Fredman y Bruce Weide (1978) demostraron posteriormente que este algoritmo, basado en la clasificación de los intervalos, era óptimo. ${\displaystyle O(n\log n)}$

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 un algoritmo de complejidad, ahora conocido como algoritmo de Bentley , basado en reducir el problema a n problemas unidimensionales : esto se hace barriendo una línea vertical a través del área. Usando este método, el área de la unión puede calcularse sin construir explícitamente la unión en sí. Ahora también se sabe que el algoritmo de Bentley es óptimo (en el caso bidimensional), y se usa en gráficos por computadora , entre otras áreas. ${\displaystyle O(n\log n)}$

Estos dos problemas son los casos unidimensionales y bidimensionales de una cuestión más general: dada una colección de rangos rectangulares de dimensión n -d , 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 . 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 para d ≥ 3 mediante el uso de árboles cuádruples dinámicos . ${\displaystyle O(n^{d-1}\log n)}$ ${\displaystyle O(n^{d-1})}$

En 1988, Mark Overmars y Chee Yap propusieron un 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 agregar esos componentes de manera eficiente; los problemas bidimensionales en sí se resuelven de manera eficiente utilizando una estructura de enrejado . Aunque asintóticamente más rápido que el algoritmo de Bentley, sus estructuras de datos utilizan significativamente 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. ${\displaystyle O(n^{d/2}\log n)}$

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 tiempo de ejecución mejor conocido para d ≥ 3 a . ${\displaystyle O(n^{d/2})}$

Límites conocidos

El único límite inferior conocido para cualquier d es , y se conocen algoritmos óptimos con este tiempo de ejecución para d = 1 y d = 2. El algoritmo de Chan proporciona un límite superior de para d ≥ 3, por lo que para d ≥ 3, sigue siendo una cuestión abierta si son posibles algoritmos más rápidos o, alternativamente, si se pueden demostrar límites inferiores más estrictos. En particular, sigue siendo abierta la cuestión de si el tiempo de ejecución del algoritmo debe depender de d . Además, sigue abierta la cuestión de si existen algoritmos más rápidos que puedan tratar casos especiales (por ejemplo, cuando las coordenadas de entrada son números enteros dentro de un rango acotado). ${\displaystyle \Omega (n\log n)}$ ${\displaystyle O(n^{d/2})}$

El problema de medida de Klee 1D (unión de intervalos) se puede resolver en donde p denota el número de puntos de perforación necesarios para perforar todos los intervalos ^[1] (la unión de intervalos perforados 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 medida de Klee. ${\displaystyle O(n\log p)}$

Véase también

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

Referencias y lecturas adicionales

Documentos importantes

• Klee, Victor (1977), "¿Puede calcularse la medida de en menos de pasos?", American Mathematical Monthly , 84 (4): 284–285, doi :10.2307/2318871, JSTOR  2318871, MR  0436661 ${\displaystyle \cup [a_{i},b_{i}]}$ ${\displaystyle O(n\log n)}$.
• Bentley, Jon L. (1977), Algoritmos para los problemas del rectángulo de Klee , Notas inéditas, Departamento de Ciencias de la Computación, Universidad Carnegie Mellon.
• Fredman, Michael L. ; Weide, Bruce (1978), "La complejidad de calcular la medida de ", Communications of the ACM , 21 (7): 540–544, doi : 10.1145/359545.359553 , MR  0495193, S2CID  16493364 ${\displaystyle \cup [a_{i},b_{i}]}$.
• van Leeuwen, Jan ; Wood, Derick (1981), "El problema de la medida para rangos rectangulares en el espacio d ", Journal of Algorithms , 2 (3): 282–300, doi :10.1016/0196-6774(81)90027-4, hdl : 1874/15897 , MR  0632450.
• Overmars, Mark H. ; Yap, Chee-Keng (1991), "Nuevos límites superiores en el problema de medida de Klee", SIAM Journal on Computing , 20 (6): 1034–1045, doi :10.1137/0220065, hdl : 1874/16614 , MR  1135747.
• Chlebus, Bogdan S. (1998), "Sobre el problema de la medida de Klee en pequeñas dimensiones", Actas de la 25.ª Conferencia sobre tendencias actuales en teoría y práctica de la informática (SOFSEM-98), Lecture Notes in Computer Science , vol. 1521, Berlín: Springer-Verlag, págs. 304–311, doi :10.1007/3-540-49477-4_22, ISBN 978-3-540-65260-1.
• Chan, Timothy M. (2013), "El problema de la medida de Klee simplificado", Actas del 54.º Simposio IEEE sobre Fundamentos de la informática (FOCS) (PDF) , pp. 410–419, CiteSeerX  10.1.1.643.26 , doi :10.1109/FOCS.2013.51, ISBN 978-0-7695-5135-7, Número de identificación del sujeto  11648588.

Literatura secundaria

• Franco P. Preparata y Michael I. Shamos (1985). Geometría computacional (Springer-Verlag, Berlín).
• Problema de la medida de Klee, de la lista de problemas abiertos en geometría computacional del profesor Jeff Erickson. (Consultado el 8 de noviembre de 2005, cuando la última actualización fue el 31 de julio de 1998.)

Referencias

1. "Geometría computacional adaptativa", F. Nielsen, pdf
2. "Apuñalamiento rápido de cajas en grandes dimensiones", F. Nielsen, Theoretical Computer Science Volumen 246, números 1 y 2, 6 de septiembre de 2000, páginas 53-72 pdf