Problema de la medida de Klee

Algoritmo de medida de Klee
	; Un conjunto de intervalos en 2D.
Problema que resuelve	Calcular el área de la unión de un conjunto de intervalos
Estructura de datos	Árbol (teoría de grafos)
Creador	Victor Klee
Fecha	1977
Clase de complejidad	P
Tiempo de ejecución
Peor caso

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 R^d.

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

Klee, Victor (1977). Can the measure of $\cup [a_{i},b_{i}]$ be computed in less than $O(n\log n)$ steps? (84). pp. 284-285. |fechaacceso= requiere |url= (ayuda)

Jon L. Bentley (1977). Algorithms for Klee's rectangle problems. Unpublished notes, Computer Science Department, Carnegie Mellon University.
Fredman, Michael L.; Weide, Bruce (1978), «The complexity of computing the measure of $\cup [a_{i},b_{i}]$ », Communications of the ACM 21: 540-544, MR 0495193, doi:10.1145/359545.359553.
van Leeuwen, Jan; Wood, Derick (1981), «The measure problem for rectangular ranges in d-space», Journal of Algorithms 2: 282-300, MR 0632450, doi:10.1016/0196-6774(81)90027-4..
Overmars, Mark H.; Yap, Chee-Keng (1991), «New upper bounds in Klee's measure problem», SIAM Journal on Computing 20 (6): 1034-1045, MR 1135747, doi:10.1137/0220065.. (PDF of the tech report version.)
Chlebus, Bogdan S. (1998), «On the Klee's measure problem in small dimensions», Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM-98), Lecture Notes in Computer Science 1521, Berlin: Springer-Verlag, pp. 304-311, doi:10.1007/3-540-49477-4_22..
Chan, Timothy M. (2013), «Klee's measure problem made easy», 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.)

Datos: Q6420068

Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.

[Klee77-1] Klee, Victor (1977). Can the measure of $\cup [a_{i},b_{i}]$ be computed in less than $O(n\log n)$ steps? (84). pp. 284-285. |fechaacceso= requiere |url= (ayuda)