Anar al contingut

Problema de la mida de Klee

De L'Enciclopèdia, la wikipedia en valencià
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 Rd.

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)[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

  1. ↑ Klee, Victor(1977).«Ca the measure of ∪[ai,bi] be computed in less than O(nlog⁡n) steps?».(84): 284-285.Consultat el 13 de febrer de 2017.


Referències