Separación de un poliedro preprocesado y un plano.

Tengo serios problemas para comprender un paso en el documento de Dobkin y Kirkpatrick sobre la separación de los poliedros. Estoy tratando de entender esta versión: http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/old%20papers/DPD+Kirk.pdf

Se argumenta que después de que conocemos la mejor separación de y , realizado por y , podemos encontrar la mejor separación de y en pasos. Esto se hace de la siguiente manera. Tomamos el plano paralelo a través de y cortamos en dos partes con él. Por un lado, el punto más cercano a es y por el otro tenemos un poliedro `` elemental '' que podemos verificar en el tiempo . Mi problema es: ¿cómo encontramos este poliedro elemental? Tenga en cuenta que el grado de $P_{i}$ $S$ $r_i$ $s_i$ $P_{i-1}$ $S$ $O(1)$ $S$ $r_i$ $P_{i-1}$ $S$ $r_i$ $O(1)$ $r_i$ en $P_{i-1}$ puede ser ilimitado.

En el pdf para probar Thm 5.1 de la página 9, usan Thm 3.1 de la página 4, lo que hace que todo sea más difícil de seguir.

ds.algorithms cg.comp-geom domotorp
fuente

Realmente me pregunto si ofrezco una recompensa en la descripción de la cual digo que la respuesta de JeffE no es clara para mí y, en un comentario a su respuesta, especifico mi problema, entonces ¿por qué la gente sigue votando su respuesta sin responder mi pregunta? ¿pregunta? Además, me pregunto, ¿su respuesta obtendría la recompensa automáticamente?

domotorp

un voto positivo indica que la respuesta proporciona algo de valor, ¡lo cual hizo! simplemente no exactamente lo que querías. de hecho, la respuesta que necesitaba parecía ser un refinamiento de la sugerencia general. Además, ¿por qué preocuparse por los votos a favor de otra persona?

Suresh Venkat

Respuestas:

Respuesta actualizada y reescrita desde cero.

Se le da un politopo . Ejecutar la jerarquía Dobkin-KIRKPATRIC en P. Esto le da una secuencia de polytops . Supongamos que desea encontrar el punto más cercano en a un punto de consulta . El algoritmo básico comienza calculando el punto más cercano a en , luego considera todas las nuevas regiones (carpas) adyacentes a , encuentra el punto más cercano a en estas nuevas regiones y continúa de esta manera hasta llegar a . $P$ $P_1 \subseteq P_2 \subseteq \ldots \subseteq P_k = P$ $P$ $q$ $c_1$ $q$ $P_1$ $c_1$ $c_2$ $q$ $P_k$

Ahora, si está en un borde, entonces no hay problema: solo dos carpas pueden tocar este borde, o solo una de ellas puede cubrir el borde. Como tal, actualizar desde en este caso lleva tiempo constante. $c_i$ $c_{i+1}$ $C_i$

Entonces, el problema es cuando encuentra en un vértice de alto grado, porque entonces el número de nuevas tiendas adyacentes a él cuando se mueve a puede ser grande. Para superar esto, vamos a simular un vértice de alto grado como una colección de vértices de bajo grado. En particular, en cada etapa, si encuentra en un vértice , vamos a recordar dos aristas consecutivas adyacentes a , de modo que el punto más cercano a en encuentra en una carpa que es adyacente o cubre uno de estos dos bordes. Como tal, podemos hacer el cálculo requerido en tiempo constante. $c_i$ $P_{i+1}$ $c_i$ $v$ $e_i, e_i'$ $v$ $q$ $P_{i+1}$

Así que seguimos con el problema de cómo hacer un seguimiento de estos dos bordes a medida que subimos.

Para hacer eso, precalcule para cada vértice de una dirección tangente . Deje ser el polígono convexo que es la figura del vértice de para el polígono (con el plano que define la figura del vértice tiene normal en la dirección de ). Conceptualmente, comporta como una jerarquía 2d DK. Si el punto más cercano en a encuentra en un vértice entonces esto corresponde a y un borde adyacente en , donde el borde $v$ $P$ $t_v$ $Q_i(v)$ $v$ $P_i$ $t_v$ $Q_1(v), Q_2(v), ..., Q_k(v)$ $Q_i(v)$ $q$ $w$ $v$ $e$ $P_i$ $e$ interseca el plano de la figura del vértice en . Si el punto más cercano en a encuentra en un borde , entonces recuerda los dos bordes adyacentes de que definen los dos vértices de (aquí pertenece a ). $w$ $Q_i(v)$ $q$ $e'$ $P_i$ $e'$ $e'$ $Q_i(v)$

Y ahora hemos terminado ... De hecho, si también está en entonces podemos actualizarlo en tiempo constante (ya que esto es solo una jerarquía 2d DK). Si, por otro lado, ya no está en entonces debe pertenecer a una nueva tienda adyacente o que cubra el punto anterior . En cualquier caso, podemos actualizarlo en tiempo constante. $c_{i+1}$ $Q_{i+1}(v)$ $c_{i+1}$ $Q_{i+1}(v)$ $c_{i}$

Sariel Har-Peled
fuente

Respuesta actualizada A ver si tiene sentido ahora. Esta es la forma en que pienso sobre esta estructura de datos. Es posible que no tenga relación con lo que está en el documento.

Sariel Har-Peled

Ahora entiendo, gracias! ¡Entonces el truco es que elegimos las direcciones tangentes al principio y las mantenemos sin cambios todo el tiempo! He eliminado mis comentarios anteriores que estaban relacionados con su respuesta anterior. Gracias una vez mas!

domotorp

Si. ¡Feliz de ayudar!

Sariel Har-Peled

El teorema 3.1 requiere que la representación jerárquica de sea compacta . Uno de los requisitos para la compacidad es que el grado de en está limitado por una constante. Vea la parte inferior de la página 3. $P$ $r_i$ $P_{i-1}$

La definición y construcción de la jerarquía Dobkin-Kirkpatrick es mucho más explícita en sus documentos anteriores (referencias [9,10,11] en el documento que está leyendo). Recomiendo leerlos primero.

Jeffε
fuente

Creo que garantizan que el grado de vértices en está acotado. No veo cómo podría asegurarse de que el grado de

esté limitado. Si, por ejemplo, tiene un poliedro donde dos vértices están conectados a cada vértice, ¿cómo puede comenzar?

P_{i - 1} ∖ P_{i}

$P_{i-1}\setminus P_i$

r_{i}

$r_i$

domotorp

Con uno de los otros vértices, todos con grado 4. (De hecho, con un subconjunto independiente de los vértices de grado 4). El punto

es un vértice de

pero no un vértice de

r_{i}

$r_i$

P_{i - 1}

$P_{i-1}$

P_{i}

$P_i$

Jeffε

Entonces está el malentendido. Creo que

es un vértice de

, así como en el algoritmo que he descrito, en particular, el más cercano a

. ¿Me equivoco?

r_{i}

$r_i$

P_{i}

$P_i$

S

$S$

domotorp

Este parece ser uno de estos supuestos de posición general estándar pero tedioso. Si no le importa el tiempo de ejecución, siempre puede reemplazar un vértice de grado

por dos vértices extremadamente cercanos de grado

(si insiste en las caras triangulares). Repita esto hasta que todos los vértices hasta que todos los grados sean menores que 10.

d

$d$

d / 2 + 3

$d/2 + 3$

Sariel Har-Peled

@Sariel: Estaba pensando lo mismo, pero ¿por qué terminaría el proceso? Tenga en cuenta que cuando eliminamos un vértice, es posible que sus vecinos no formen una cara, por lo que podríamos tener que agregar nuevos bordes, de hecho, podríamos tener que aumentar el grado de un vértice.

domotorp

En caso de que a alguien todavía le interese la pregunta: el inconveniente de la explicación de Dobkin Kirpatrick también se ha señalado en la detección óptima de intersecciones entre poliedros convexos de Barba y Langerman .

Observan en el documento (versión SODA 2015, no arxiv) que la Geometría computacional de O'Rourke en C , cap. 7 ya detalla una solución (que es esencialmente la respuesta de Sariel). El documento de SODA también presenta una solución alternativa; definiendo una variante de la jerarquía DK en la que cada vértice tiene un grado acotado.

Joseph Stack
fuente