Séparation d'un polyèdre prétraité et d'un plan

14

J'ai de la difficulté à comprendre une étape dans le document de Dobkin et Kirkpatrick sur la séparation des polyèdres. J'essaie de comprendre cette version: http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/old%20papers/DPD+Kirk.pdf

Il soutient qu'après avoir connu la meilleure séparation de et S , réalisée par r i et s i , nous pouvons trouver la meilleure séparation de P i - 1 et S dans les étapes O ( 1 ) . Cela se fait de la manière suivante. Nous prenons l'avion parallèle à S par r i et coupons P i - 1 en deux parties avec lui. D'un côté, le point le plus proche de S est r iPjeSrjesjePje-1SO(1)SrjePje-1Srjeet de l'autre nous avons un polyèdre `` élémentaire '' que nous pouvons vérifier en temps . Mon problème est - comment trouver ce polyèdre élémentaire? Notez que le degré de r i dans P i - 1 peut être illimité.O(1)riPi1

Dans le pdf pour prouver Thm 5.1 de la page 9, ils utilisent Thm 3.1 de la page 4, ce qui rend le tout plus difficile à suivre.

domotorp
la source
Je me demande vraiment si si j'offre une prime dans la description de laquelle je dis que la réponse de JeffE n'est pas claire pour moi et dans un commentaire sur sa réponse, je précise mon problème, alors pourquoi les gens continuent-ils à voter pour sa réponse sans répondre à ma question? Aussi, je me demande, sa réponse obtiendrait-elle automatiquement la prime?
domotorp
un vote positif indique que la réponse fournit quelque chose de valeur, ce qu'elle a fait! tout simplement pas exactement ce que vous vouliez. en fait, la réponse dont vous aviez besoin semblait être un raffinement de la suggestion générale. Aussi, pourquoi s'inquiéter des votes positifs de quelqu'un d'autre?
Suresh Venkat

Réponses:

6

Réponse mise à jour et réécrite à partir de zéro.

On vous donne un polytope . Exécutez la hiérarchie Dobkin-Kirkpatric sur P. Cela vous donne une séquence de polytops P 1P 2... P k = P . Supposons que vous souhaitiez trouver le point le plus proche sur P d'un point de requête q . L'algorithme de base commence par calculer le point le plus proche c 1 à q sur P 1 , puis il considère toutes les nouvelles régions (tentes) adjacentes àPP1P2Pk=PPqc1qP1 , trouve le point le plus proche c 2 à qc1c2qdans ces nouvelles régions, et continuer de cette façon jusqu'à atteindre .Pk

Maintenant, si est sur un bord, alors il n'y a pas de problème - seules deux tentes peuvent toucher ce bord, ou une seule d'entre elles peut couvrir le bord. En tant que tel, la mise à jour de c i + 1 à partir de C i dans ce cas prend un temps constant.cjecje+1Cje

Le problème est donc lorsque se trouve sur un sommet de haut degré, car alors le nombre de nouvelles tentes adjacentes lors du passage à P i + 1 peut être important. Pour surmonter cela, nous allons simuler un sommet de grand degré comme une collection de sommets de faible degré. En particulier, à chaque étape, si c i se situe sur un sommet v , on va se souvenir de deux arêtes consécutives e i , e i adjacentes à v , de sorte que le point le plus proche de q dans P i + 1cjePje+1cjeveje,ejevqPi+1repose sur une tente qui est adjacente ou couvre l'un de ces deux bords. En tant que tel, nous pouvons faire le calcul requis en temps constant.

Donc, nous restons avec le problème de savoir comment garder une trace de ces deux bords lorsque nous montons.

Pour ce faire, pré-calculer pour chaque sommet de P une direction tangente t v . Soit Q i ( v ) le polygone convexe qui est la figure de sommet de v pour le polygone P i (le plan définissant la figure de sommet ayant une normale dans la direction de t v ). Conceptuellement, Q 1 ( v ) , Q 2 ( v ) , . . vPtvQi(v)vPitvQ1(v),Q2(v),...,Qk(v)se comporte comme une hiérarchie 2D 2D. Si le point le plus proche sur à q se trouve sur un sommet w, cela correspond à v et à une arête adjacente e dans P i , où l'arête e coupe le plan de la figure de sommet en w . Si le point le plus proche sur Q i ( v ) à q se situe sur une arête e , alors vous vous souvenez des deux arêtes adjacentes de P i qui définissent les deux sommets de e (iciQi(v)qwvePiewQi(v)qePie appartiennent àe ).Qi(v)

Et maintenant, nous avons terminé ... En effet, si est également sur Q i + 1 ( v ), nous pouvons le mettre à jour en temps constant (car ce n'est qu'une hiérarchie DK 2d). Si par contre c i + 1 n'est plus sur Q i + 1 ( v ) alors elle doit appartenir à une nouvelle tente adjacente ou couvrant le point précédent c i . Dans les deux cas, nous pouvons le mettre à jour en temps constant.ci+1Qi+1(v)ci+1Qi+1(v)ci

Sariel Har-Peled
la source
Réponse mise à jour. Voyez si cela a un sens maintenant. C'est ainsi que je pense à cette structure de données. Cela pourrait n'avoir aucun rapport avec le contenu du document.
Sariel Har-Peled
Je comprends maintenant, merci! Donc, l'astuce est que nous choisissons les directions tangentes au début et les gardons inchangées tout le temps! J'ai supprimé mes commentaires précédents liés à votre ancienne réponse. Merci encore!
domotorp
Oui. Heureux d'aider!
Sariel Har-Peled
8

Le théorème 3.1 exige que la représentation hiérarchique de soit compacte . L'une des exigences de compacité est que le degré de r i dans P i - 1 soit limité par une constante. Voir le bas de la page 3.PriPi1

La définition et la construction de la hiérarchie Dobkin-Kirkpatrick sont beaucoup plus explicites dans leurs articles précédents (références [9,10,11] dans l'article que vous lisez). Je recommande fortement de les lire d'abord.

Jeffε
la source
Je pense qu'ils garantissent que le degré de sommets dans est borné. Je ne vois pas comment vous pourriez vous assurer que le degré de r i est borné. Si, par exemple, vous avez un polyèdre où deux sommets sont connectés à chaque sommet, comment pouvez-vous commencer? Pi1Piri
domotorp
1
Avec l'un des autres sommets, qui ont tous le degré 4. (En fait, avec un sous-ensemble indépendant des sommets de degré 4). Le point est un sommet de P i - 1 mais pas un sommet de P i . riPi1Pi
Jeffε
Il y a donc un malentendu. Je pense que est un sommet de P i et dans l'algorithme que je décrit, en particulier le plus proche de S . Ai-je tort? riPiS
domotorp
/2+3
@Sariel: Je pensais la même chose, mais alors pourquoi le processus se terminerait-il? Notez que lorsque nous supprimons un sommet, ses voisins peuvent ne pas former de face, il nous faudra donc peut-être ajouter de nouveaux bords, en fait, nous devrons peut-être augmenter le degré d'un sommet.
domotorp
1

Dans le cas où quelqu'un serait toujours intéressé par la question: le problème de l'explication Dobkin Kirpatrick a également été souligné dans Barba et Langerman Optimal detection of intersections between convex polyhedra .

Ils observent dans l'article (version SODA 2015, pas arxiv) que la géométrie computationnelle d'O'Rourke en C , chap 7 détaille déjà une solution de contournement (qui est essentiellement la réponse de Sariel). Le document SODA présente également une solution alternative; définir une variante de la hiérarchie DK dans laquelle chaque sommet a un degré borné.

Joseph Stack
la source