Problema de la medida de Klee

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Algoritmo de medida de Klee
Set of rectangles (Klee's Trellis).svg
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
[editar datos en Wikidata]


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[editar]

  1. Klee, Victor (1977). Can the measure of be computed in less than steps? (84). pp. 284-285.