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.
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
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 be computed in less than 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 », Communications of the ACM21: 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 Algorithms2: 282-300, MR 0632450, doi:10.1016/0196-6774(81)90027-4..
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 Science1521, 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).
, from Professor Jeff Erickson's in computational geometry. (Accessed November 8, 2005, when the last update was July 31, 1998.)
Datos:Q6420068
Agosto 16, 2021
problema, medida, klee, geometría, computacional, problema, medida, klee, problema, determinar, cuan, eficientemente, medida, unión, multidimensional, rangos, rectangulares, puede, calculada, aquí, rango, rectangular, dimensional, definido, como, producto, car. En la geometria computacional el problema de la medida de Klee es el problema de determinar cuan eficientemente la medida de una union multidimensional de rangos rectangulares puede ser calculada Aqui un rango rectangular d dimensional es definido como un producto cartesiano de d intervalos de numeros reales que es un subconjunto de Rd Algoritmo de medida de KleeUn conjunto de intervalos en 2D Problema que resuelveCalcular el area de la union de un conjunto de intervalosEstructura de datosArbol teoria de grafos CreadorVictor KleeFecha1977Clase de complejidadPTiempo de ejecucionPeor casoO N log N displaystyle O N log N editar datos en Wikidata Este problema toma el nombre en honor a Victor Klee quien dio un algoritmo para calcular la longitud de una union de intervalos el caso d 1 1 que mas tarde mostro ser optimamente eficiente en el sentido de la teoria de complejidad computacional La complejidad computacional para calcular el area de una union de rangos rectangulares 2 dimensionales ahora tambien es conocida pero en el caso de d 3 sigue siendo un problema abierto Referencias y lectura adicional Editar Klee Victor 1977 Can the measure of a i b i displaystyle cup a i b i be computed in less than O n log n displaystyle 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 a i b i displaystyle 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 Q6420068Obtenido de https es wikipedia org w index php title Problema de la medida de Klee amp oldid 122637519, wikipedia, wiki, leyendo, leer, libro, biblioteca,
