Separação de um poliedro pré-processado e um plano

Tenho sérios problemas para entender um passo do artigo de Dobkin e Kirkpatrick sobre a separação dos poliedros. Estou tentando entender esta versão: http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/old%20papers/DPD+Kirk.pdf

Argumenta que, depois de conhecermos a melhor separação de e , realizada por e , podemos encontrar a melhor separação de e nos passos . Isso é feito da seguinte maneira. Pegamos o plano paralelo a através de e cortamos em duas partes. Por um lado, o ponto mais próximo de é e, por outro, temos um poliedro `` elementar '' que podemos verificar no tempo . Meu problema é - como encontramos esse poliedro elementar? Observe que o grau 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$ em pode ser ilimitada. $P_{i-1}$

No pdf para provar Thm 5.1 da página 9, eles usam Thm 3.1 da página 4, o que dificulta tudo.

ds.algorithms cg.comp-geom domotorp
fonte

Eu realmente me pergunto se, se ofereço uma recompensa na descrição da qual digo que a resposta de JeffE não está clara para mim e, em um comentário à sua resposta, eu especifico meu problema com ela, por que as pessoas continuam votando sua resposta sem responder à minha pergunta? questão? Além disso, eu me pergunto, a resposta dele receberia a recompensa automaticamente?

Domotorp

um voto positivo indica que a resposta fornece algo de valor, o que deu! apenas não exatamente o que você queria. de fato, a resposta que você precisava parecia ser um refinamento da sugestão geral. Além disso, por que se preocupar com os votos de outra pessoa?

Suresh Venkat

Respostas:

Resposta atualizada e reescrita do zero.

Você recebe um politopo . Executar a hierarquia Dobkin-Kirkpatric em P. Isto dá-lhe uma sequência de polytops . Vamos supor que você gostaria de encontrar o ponto mais próximo em de um ponto de consulta . O algoritmo básico começa calculando o ponto mais próximo a em , depois considera todas as novas regiões (tendas) adjacentes a , encontre o ponto mais próximo 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$ nessas novas regiões e continue dessa maneira até chegarmos a . $P_k$

Agora, se aparece sobre uma borda, então não há nenhum problema - apenas duas tendas pode tocar neste borda, ou apenas um deles pode cobrir a borda. Como tal, a actualização a partir de , neste caso, leva tempo constante. $c_i$ $c_{i+1}$ $C_i$

Assim, o problema é quando encontra-se em um vértice de grau elevado, porque então o número de novas tendas adjacentes para que quando em movimento para pode ser grande. Para superar isso, vamos simular um vértice de alto grau como uma coleção de vértices de baixo grau. Em particular, em cada estágio, se encontrar em um vértice , lembraremos de duas arestas consecutivas adjacentes a , de modo que o ponto mais próximo de em $c_i$ $P_{i+1}$ $c_i$ $v$ $e_i, e_i'$ $v$ $q$ $P_{i+1}$ fica em uma barraca adjacente ou que cobre uma dessas duas arestas. Como tal, podemos fazer o cálculo necessário em tempo constante.

Portanto, continuamos com o problema de como acompanhar essas duas arestas à medida que subimos.

Para fazer isso, pré-calcule para cada vértice de uma direção tangente . Seja o polígono convexo que é a figura de vértice de para o polígono (com o plano que define que a figura de vértice tem normal na direção de ). Conceptualmente, $v$ $P$ $t_v$ $Q_i(v)$ $v$ $P_i$ $t_v$ $Q_1(v), Q_2(v), ..., Q_k(v)$ se comporta como uma hierarquia 2D DK. Se o ponto mais próximo de a estiver em um vértice , isso corresponderá a uma aresta adjacente em , onde a aresta cruza o plano da figura do vértice em . Se o ponto mais próximo do para encontra-se em uma vantagem , então você lembrar as duas bordas adjacentes de que definem os dois vértices de (aqui $Q_i(v)$ $q$ $w$ $v$ $e$ $P_i$ $e$ $w$ $Q_i(v)$ $q$ $e'$ $P_i$ $e'$ pertence a ). $e'$ $Q_i(v)$

E agora estamos a fazer ... Na verdade, se é também sobre , então podemos atualizado em tempo constante (uma vez que esta é apenas uma hierarquia DK 2d). Se, por outro lado, não estiver mais em , ele deverá pertencer a uma nova barraca adjacente ou que cubra o ponto anterior . Em ambos os casos, podemos atualizá-lo em tempo constante. $c_{i+1}$ $Q_{i+1}(v)$ $c_{i+1}$ $Q_{i+1}(v)$ $c_{i}$

Sariel Har-Peled
fonte

Resposta atualizada. Veja se faz algum sentido agora. É assim que penso sobre essa estrutura de dados. Pode não ter relação com o que está no jornal.

Sariel Har-Peled

Eu entendo agora, obrigado! Portanto, o truque é escolher as direções tangentes no início e mantê-las inalteradas o tempo todo! Excluí meus comentários anteriores relacionados à sua resposta antiga. Obrigado mais uma vez!

Domotorp

Sim. Feliz por ajudar!

Sariel Har-Peled

O teorema 3.1 requer que a representação hierárquica de seja compacta . Um dos requisitos de compacidade é que o grau de em é delimitada por uma constante. Veja a parte inferior da página 3. $P$ $r_i$ $P_{i-1}$

A definição e construção da hierarquia de Dobkin-Kirkpatrick é muito mais explícita em seus artigos anteriores (referências [9,10,11] no artigo que você está lendo). Eu recomendo a leitura deles primeiro.

Jeffε
fonte

Penso que eles garantem que o grau de vértices em

seja limitado. Eu não vejo como você pode certificar-se o grau de

é limitado. Se, por exemplo, você tem um poliedro em que dois vértices estão conectados a cada vértice, como você pode começar?

P_{i - 1} ∖ P_{i}

$P_{i-1}\setminus P_i$

r_{i}

$r_i$

Domotorp

(. De facto, com um subconjunto independente do grau 4-vértices) com um dos outros vértices, que todos têm um grau 4. O ponto

representa um vértice de

, mas não um vértice de

r_{i}

$r_i$

P_{i - 1}

$P_{i-1}$

P_{i}

$P_i$

Jeffε

Portanto, há um mal-entendido. Eu acho que

é um vértice de

, bem como no algoritmo que eu descrevi, nomeadamente a mais próxima de

. Estou errado?

r_{i}

$r_i$

P_{i}

$P_i$

S

$S$

Domotorp 7/12

Esse parece ser um desses pressupostos de posição geral padrão, mas tedioso. Se você não se importa com o tempo de execução, sempre pode substituir um vértice de grau

por dois vértices extremamente próximos de grau

(se você insistir em faces triangulares). Repita isso até todos os vértices até que todos os graus são menores do que 10.

d

$d$

d / 2 + 3

$d/2 + 3$

Sariel Har-Peled

@Sariel: Eu estava pensando o mesmo, mas então por que o processo terminaria? Observe que, quando excluímos um vértice, seus vizinhos podem não formar uma face; portanto, podemos ter que adicionar novas arestas; na verdade, talvez tenhamos que aumentar o grau de um vértice.

Domotorp

Caso alguém ainda esteja interessado na pergunta: o obstáculo na explicação de Dobkin Kirpatrick também foi apontado na detecção ótima de Barba e Langerman de interseções entre poliedros convexos .

Eles observam no artigo (versão SODA 2015, não arxiv) que a Geometria Computacional de O'Rourke em C , cap. 7, já detalha uma solução alternativa (que é essencialmente a resposta de Sariel). O documento SODA também apresenta uma solução alternativa; definindo uma variante da hierarquia DK na qual cada vértice tem grau delimitado.

Joseph Stack
fonte