En geometría computacional , el problema de medida de Klee es el problema de determinar qué tan 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 lleva el nombre de Victor Klee , quien proporcionó 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 línea real , calcule 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 declaración. Michael Fredman y Bruce Weide (1978) demostraron más tarde que este algoritmo, basado en ordenar los intervalos, era óptimo.
Más tarde, en 1977, Jon Bentley consideró un análogo bidimensional de este problema: dada una colección de n rectángulos , encuentre el área de su unión. También obtuvo una complejidadalgoritmo, ahora conocido como algoritmo de Bentley , basado en reducir el problema a problemas n 1- dimensionales: esto se hace barriendo una línea vertical a través del área. Con este método, el área de la unión se puede calcular 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 utiliza en gráficos por computadora , entre otras áreas.
Estos dos problemas son los casos de 1 y 2 dimensiones de una pregunta más general: dada una colección de rangos rectangulares de n d -dimensiones, calcule la medida de su unión. Este problema general es el problema de 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 óptima, ya que sólo se descompone el d -dimensional problema en n ( d-1 ) problemas dimensionales, y no se descompone adicionalmente esos subproblemas. En 1981, Jan van Leeuwen y Derek Wood mejoraron el tiempo de ejecución de este algoritmo parapara d ≥ 3 mediante el uso de quadtrees dinámicos .
En 1988, Mark Overmars y Chee Yap propusieron unaalgoritmo 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í mismos 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 usa en problemas donde n o d es grande. 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 tiempo de ejecución más conocido para d ≥ 3 a .
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 yd = 2. El algoritmo Chan proporciona un límite superior depara d ≥ 3, por lo que para d ≥ 3, sigue siendo una pregunta abierta si son posibles algoritmos más rápidos o, alternativamente, si se pueden probar límites inferiores más estrictos. En particular, permanece abierto si el tiempo de ejecución del algoritmo debe depender de d . Además, la cuestión de si existen algoritmos más rápidos que puedan tratar con casos especiales (por ejemplo, cuando las coordenadas de entrada son números enteros dentro de un rango limitado) permanece abierta.
El problema de medida de 1D Klee (unión de intervalos) se puede resolver en donde p denota el número de puntos de perforación necesarios para apuñalar 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.
Ver también
- Aproximación de volumen convexo , un algoritmo eficiente para cuerpos convexos
Referencias y lecturas adicionales
Papeles importantes
- Klee, Victor (1977), "¿Puede la medida de ser calculado en menos de pasos? ", American Mathematical Monthly , 84 (4): 284-285, doi : 10.2307 / 2318871 , JSTOR 2318871 , MR 0436661.
- Bentley, Jon L. (1977), Algoritmos para los problemas de rectángulos de Klee , Notas no publicadas, Departamento de Ciencias de la Computación, Universidad Carnegie Mellon.
- Fredman, Michael L .; Weide, Bruce (1978), "La complejidad de calcular la medida de", Comunicaciones del ACM , 21 (7): 540–544, doi : 10.1145 / 359545.359553 , MR 0495193 , S2CID 16493364.
- 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 25a Conferencia sobre Tendencias Actuales en Teoría y Práctica de la Informática (SOFSEM-98) , Lecture Notes in Computer Science , 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 se hizo fácil", Actas del 54º Simposio IEEE sobre Fundamentos de la Ciencia de la Computación (FOCS) (PDF) , págs. 410–419, CiteSeerX 10.1.1.643.26 , doi : 10.1109 / FOCS.2013.51 , ISBN 978-0-7695-5135-7, S2CID 11648588.
Literatura secundaria
- Franco P. Preparata y Michael I. Shamos (1985). Geometría computacional (Springer-Verlag, Berlín).
- El problema de la medida de Klee , de la lista de problemas abiertos del profesor Jeff Erickson en geometría computacional. (Consultado el 8 de noviembre de 2005, cuando la última actualización fue el 31 de julio de 1998.)
Referencias
- ^ "Geometría computacional adaptativa", F. Nielsen, pdf
- ^ "Rápido apuñalamiento de cajas en grandes dimensiones", F. Nielsen, Theoretical Computer Science Volume 246, Issues 1-2, 6 de septiembre de 2000, páginas 53-72 pdf