Encuentra un cubo más grande contenido en la unión de cuboides

18

Tengo muchos cuboides en el espacio 3D, cada uno tiene un punto de partida en (x, y, z) y tiene un tamaño de (Lx, Ly, Lz). Me pregunto cómo encontrar un cubo más grande en este espacio 3D contenido en la unión de los cuboides. ¿Existe un algoritmo eficiente para esto?

Por ejemplo, si tengo los siguientes cuboides:

  • un cuboide que comienza en (0,0,0) con tamaño (10,10,10),
  • un cuboide en (10,0,0) con tamaño (12,13,15),
  • un cuboide en (0,10,0) con tamaño (10,10,10),
  • un cuboide en (0,0,10) con tamaño (10,10,10), y
  • un cuboide en (10,10,10) con tamaño (9,9,9).

Entonces, el cubo más grande contenido en la unión de estos cuboides será un cubo que comienza en (0,0,0) con un tamaño (19,19,19).

Una versión más general de esta pregunta:

Dada una colección de cajas en , encuentre el hipercubo más grande contenido dentro de la unión de las cajas.R dnRd

pantoffski
fuente
8
Creo que hay una mejor pregunta oculta en el interior: a saber, dada una unión de cajas en , calcule el hipercubo más grande contenido dentro de la unión. Rd
Suresh Venkat
1
¿Se pueden superponer estos cuboides?
Peter Boothe
@Suresh, gracias por aclarar y generalizar la pregunta :) @Peter, en mi caso ... No se superpondrá :)
pantoffski
2
Por la forma en que lo has escrito, parece que los lados de los cubos están alineados con los ejes x, y y z. ¿Es este el caso, o pueden los cubos tener orientaciones arbitrarias? Obviamente, esto hace una diferencia significativa en la eficiencia del algoritmo.
Joe Fitzsimons
En mi caso, la cara de cada cuboide es ortogonal a los ejes solamente.
pantoffski

Respuestas:

15

Bueno, aquí hay una primera respuesta tonta ... Tome un avión a través de cada cara de las cajas rectangulares. Esto forma una cuadrícula de tamaño . No es difícil calcular para cada celda de la cuadrícula, ya sea dentro o fuera de la unión. Ahora, desde cada vértice de la cuadrícula, haga crecer un cubo (que tenga este vértice como vértice) tratando de hacerlo lo más grande posible. Al hacerlo de la manera más ingenua, esto toma tiempo por vértice, pero probablemente usando magia de búsqueda de rango ortogonal, uno debería poder hacerlo en per vértice. Entonces debería ser posible ...O ( n 3 log n ) log O ( 1 ) n O ( n 3 log O ( 1 ) n )O(n3)O(n3logn)logO(1)nO(n3logO(1)n)

Un segundo intento: calcular la unión. En este caso específico, esto se puede hacer en tiempo (barriendo planos). Ahora, observe que solo necesita calcular el diagrama voronoi del límite de la unión. Usando el resultado: http://vw.stanford.edu/~vladlen/publications/vor-polyhedral.pdf , esto puede hacerse en tiempo , para una pequeña constante arbitraria .L O ( n 2 + ε ) ε > 0O(nlogn)LO(n2+ε)ε>0

Romper el tiempo de ejecución vinculado aquí sería interesante, en mi humilde opinión.O(n2)

Sariel Har-Peled
fuente
Gracias señor, también creo que L∞ es la mejor solución para este problema hasta ahora. Desde que hice el caso L∞ para 2D antes (implementado por los métodos proporcionados en este documento inf.usi.ch/faculty/papadopoulou/publications/ijcga01.pdf ). El estuche 3D con solo cajas no debería ser muy difícil.
pantoffski
8

La respuesta a la pregunta general sobre parece ser que es NP-hard. La prueba es bastante simple. Simplemente tomamos una instancia de 3SAT en variables y asociamos cada variable con una dimensión. Piense en el espacio como un espacio de posibles asignaciones de variables: solo consideramos puntos entre -1 y +1 en cada dimensión, y asociamos ubicaciones con una asignación de 0 para esa variable y con una asignación de 1. Cada La cláusula excluye una región dada por un hipercuboide . d < 0 > 0 1 × 1 × 1 × n × n × n . . . × nRdd<0>01×1×1×n×n×n...×n

Si la unión de estos cuboides llena el espacio (y por lo tanto contiene un cubo ), entonces no hay una asignación satisfactoria de variables para la instancia 3SAT. Sin embargo, si el cubo más grande contenido es o 0 (sin cláusulas), las únicas otras posibilidades, entonces existe una asignación satisfactoria de variables.1 × 1 × . . . × 12×2×...×21×1×...×1

Joe Fitzsimons
fuente
Me imagino que puede probar que está en FNP (al menos en el caso de los cuboides alineados por ejes), ejecutando el argumento anterior en reversa y mostrando que cualquier cuboide constituye una restricción que puede verificarse en el tiempo polinómico.
Joe Fitzsimons