Problema de la medida de Klee
En la geometría computacional, el problema de la medida de Klee es el problema de determinar cuan eficientemente la medida de una unión (multidimensional) de rangos rectangulares puede ser calculada. Aquí, un rango rectangular d-dimensional es definido como un producto cartesiano de d intervalos de números reales, que es un subconjunto de Rd.
Este problema toma el nombre en honor a Victor Klee, quien dio un algoritmo para calcular la longitud de una unión de intervalos (el caso d = 1)[1] que más tarde mostró ser óptimamente eficiente en el sentido de la teoría de complejidad computacional. La complejidad computacional para calcular el área de una unión de rangos rectangulares 2-dimensionales ahora también es conocida, pero en el caso de d ≥ 3 sigue siendo un problema abierto.
Referencias y lectura adicional
- Jon L. Bentley (1977). Algorithms for Klee's rectangle problems. Unpublished notes, Computer Science Department, Carnegie Mellon University.
- Plantilla:Citation
- Plantilla:Citation.
- Plantilla:Citation. (PDF of the tech report version.)
- Plantilla:Citation.
- Plantilla:Citation.
- 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.)