Problema de la mida de Klee

Problema de la mida de Klee

En la geometria computacional, el problema de la mida de Klee és el problema de determinar cuan eficientemente la mida d'una unió (multidimensional) de rancs rectangulars pot ser calculada. Ací, un ranc rectangular d-dimensional és definit com un producte cartesiano de d intervals de número real, que és un subconjunt de R^d.

Este problema pren el nom en honor a Victor Klee, qui va donar un algoritme per a calcular la llongitut d'una unió d'intervals (el cas d = 1) que més vesprada va mostrar ser óptimamente eficient en el sentit de la teoria de complexitat computacional. La complexitat computacional per a calcular l'àrea d'una unió de rancs rectangulars 2-dimensionals ara també és coneguda, pero en el cas de d ≥ 3 seguix sent un problema obert.

Referències i llectura adicional

• Jon L. Bentley (1977). Algorithms for Klee's rectangle problems. Unpublished notes, Computer Science Department, Carnegie Mellon University.
• (1978).«The complexity of computing the measure of $\cup [a_i,b_i]$».Communications of the ACM.21

540–544.doi:10.1145/359545.359553.

• (1981).«The measure problem for rectangular ranges in d-space».Journal of Algorithms.2

282–300.doi:10.1016/0196-6774(81)90027-4..

• (1991).«New upper bounds in Klee's measure problem».SIAM Journal on Computing.20(6)

1034–1045.doi:10.1137/0220065.. (PDF of the tech report version.)

• (1998).«Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM-98)».Springer-Verlag.Berlin:1521

304–311.doi:10.1007/3-540-49477-4_22..

• (2013).«Proceedings of the 54th IEEE Symposium on Foundations of Computer Science (FOCS)».doi:10.1109/FOCS.2013.51..
• 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.)