Celda más grande en un arreglo

10

Q . ¿Cuál es la complejidad de encontrar la celda limitada de mayor volumen en una disposición de hiperplanos en la dimensión d ?nd

Siento que debería saber esto ... Pero no estoy encontrando una referencia definitiva.

¿Es ? ¿Qué tal la especialización d = 2 : la celda delimitada de área más grande en una disposición de líneas?Ω(nd)d=2

Joseph O'Rourke
fuente

Respuestas:

6

O(nd)1QCα1/n2m=(logn)/αQPCPO((n2/3m2/3+n+m)polylog)

αO((n+1/α+n2/3/α2/3)polylogn)αQ

Sariel Har-Peled
fuente
1
α1/n2