Trennung eines vorverarbeiteten Polyeders und einer Ebene

14

Ich habe ernsthafte Probleme, einen Schritt in der Arbeit von Dobkin und Kirkpatrick über die Trennung von Polyedern zu verstehen. Ich versuche diese Version zu verstehen: http://www.cs.princeton.edu/~dpd/Papers/SCG-09-invited/old%20papers/DPD+Kirk.pdf

Es wird argumentiert, dass wir, nachdem wir die beste Trennung von Pi und S , die durch ri und verwirklicht wird si, die beste Trennung von Pi1 und S in O(1) -Schritten finden können. Dies geschieht auf folgende Weise. Wir nehmen die Ebene parallel zu S durch ri und schneiden Pi1 in zwei Teile. Auf der einen Seite, der nächste Punkt zu S ist , riund auf der anderen Seite haben wir ein "elementares" Polyeder, das wir in O(1) Zeit überprüfen können . Mein Problem ist - wie finden wir dieses elementare Polyeder? Es ist zu beachten, dass der Grad von ri in Pi1 unbegrenzt sein kann.

Im pdf zum Nachweis von Thm 5.1 ab Seite 9 verwenden sie Thm 3.1 ab Seite 4, was es schwieriger macht, dem Ganzen zu folgen.

domotorp
quelle
Ich wundere mich wirklich, dass, wenn ich ein Kopfgeld anbiete, in dessen Beschreibung ich sage, dass JeffEs Antwort mir nicht klar ist, und in einem Kommentar zu seiner Antwort ich mein Problem damit spezifiziere, warum die Leute seine Antwort weiter abstimmen, ohne meine zu beantworten Frage? Ich frage mich auch, ob seine Antwort automatisch das Kopfgeld erhalten würde.
Domotorp
eine positive Bewertung zeigt an, dass die Antwort etwas von Wert liefert, was sie getan hat! nur nicht genau das, was du wolltest. in der Tat schien die Antwort, die Sie brauchten, eine Verfeinerung des allgemeinen Vorschlags zu sein. Warum sollte man sich auch Sorgen um die Upvotes anderer machen?
Suresh Venkat

Antworten:

6

Antwort von Grund auf aktualisiert und neu geschrieben.

Sie sind ein Polytop gegeben . Führen Sie die Dobkin-Kirkpatric-Hierarchie auf P aus. Dies gibt Ihnen eine Folge von Polytops P 1PP . Angenommen, Sie möchten den Punkt auf P finden , der einem Abfragepunkt q am nächsten liegt. Der grundlegende Algorithmus beginnt mit der Berechnung des nächstgelegenen Punkts c 1 zu q auf P 1 , dann werden alle neuen Bereiche (Zelte) neben c 1 berücksichtigtund der nächstgelegene Punkt c 2 zu q gefundenP1P2Pk=PPqc1qP1c1c2qin diesen neuen Regionen, und fahren Sie auf diese Weise fort, bis wir .Pk

Befindet sich an einer Kante, ist dies kein Problem - möglicherweise berühren nur zwei Zelte diese Kante oder nur eines von ihnen bedeckt die Kante. In diesem Fall dauert das Aktualisieren von c i + 1 von C i eine konstante Zeit.cici+1Ci

Das Problem ist also, wenn auf einem Scheitelpunkt hohen Grades liegt, weil dann die Anzahl neuer Zelte daneben, wenn nach P i übergegangen wirdci groß sein könnte. Um dies zu überwinden, simulieren wir einen Scheitelpunkt mit hohem Grad als eine Sammlung von Scheitelpunkten mit niedrigem Grad. Insbesondere werdenwir unsin jeder Phase, wenn c i auf einem Scheitelpunktv liegt, zwei aufeinanderfolgende Kanten e i , e ' i erinnern, dievbenachbart sind, so dass der nächste Punkt zuqin P i + 1 istPi+1civei,eivqPi+1liegt auf einem Zelt, das entweder angrenzend ist oder eine dieser beiden Kanten bedeckt. Daher können wir die erforderliche Berechnung in konstanter Zeit durchführen.

Wir bleiben also bei dem Problem, wie wir diese beiden Kanten beim Aufstieg im Auge behalten können.

Berechnen Sie dazu für jeden Eckpunkt von P eine Tangentenrichtung t v . Lassen Q i ( v ) das konvexe Vieleck sein , dass der Scheitelpunkt der Figur ist V für das Polygon P i (mit der Ebene definieren , die Scheitel Figur hat in der Richtung der normalen t v ). Konzeptionell, Q 1 ( v ) , Q 2 ( v ) , . . . , Q k ( v )vPtvQi(v)vPitvQ1(v),Q2(v),...,Qk(v)Verhält sich wie eine 2D-DK-Hierarchie. Liegt der nächste Punkt auf zu q auf einem Scheitelpunkt w, so entspricht dies v und einer benachbarten Kante e in P i , wobei die Kante e die Ebene der Scheitelpunktfigur bei w schneidet . Wenn der nächste Punkt von Q i ( v ) zu q auf einer Kante e 'liegt , erinnern Sie sich an die beiden benachbarten Kanten von P i , die die beiden Ecken von e ' definieren (hier)Qi(v)qwvePiewQi(v)qePie gehört zu Q i ( v ) ).eQi(v)

Und jetzt sind wir fertig ... Wenn auch auf Q i + 1 ( v ) ist, können wir es in konstanter Zeit aktualisieren (da dies nur eine 2d DK-Hierarchie ist). Wenn andererseits c i + 1 nicht mehr auf Q i + 1 ( v ) liegt , muss es zu einem neuen Zelt gehören, das benachbart ist oder den vorherigen Punkt c i abdeckt . In beiden Fällen können wir es in konstanter Zeit aktualisieren.ci+1Qi+1(v)ci+1Qi+1(v)ci

Sariel Har-Peled
quelle
Aktualisierte Antwort. Sehen Sie, ob es jetzt Sinn macht. So denke ich über diese Datenstruktur. Möglicherweise hat es keinen Bezug zu dem, was in der Zeitung steht.
Sariel Har-Peled
Ich verstehe jetzt, danke! Der Trick ist also, dass wir die Tangentenrichtungen am Anfang auswählen und die ganze Zeit unverändert lassen! Ich habe meine vorherigen Kommentare gelöscht, die sich auf Ihre alte Antwort bezogen. Nochmals vielen Dank!
Domotorp
Ja. Freue mich zu helfen!
Sariel Har-Peled
8

Satz 3.1 erfordert , dass die hierarchische Darstellung von ist kompakt . Eine der Anforderungen an die Kompaktheit ist, dass der Grad von r i in P i - 1 durch eine Konstante begrenzt ist. Siehe unten auf Seite 3.PriPi1

Die Definition und Konstruktion der Dobkin-Kirkpatrick-Hierarchie ist in ihren früheren Abhandlungen (Verweise [9,10,11] in der Abhandlung, die Sie lesen) sehr viel expliziter. Ich empfehle dringend, sie zuerst zu lesen.

Jeffε
quelle
Ich denke, dass sie garantieren, dass der Grad der Eckpunkte in begrenzt ist. Ich verstehe nicht, wie Sie sicherstellen können, dass der Grad von r i begrenzt ist. Wenn Sie beispielsweise ein Polyeder haben, bei dem zwei Eckpunkte mit jedem Eckpunkt verbunden sind, wie können Sie dann beginnen? Pi1Piri
Domotorp
1
Mit einem der anderen Scheitelpunkte, die alle Grad 4 haben. (Tatsächlich mit einer unabhängigen Teilmenge der Scheitelpunkte vom Grad 4.) Der Punkt ist ein Scheitelpunkt von P i - 1, aber kein Scheitelpunkt von P i . riPi1Pi
Jeffs
Da ist also das Missverständnis. Ich denke, dass ein Vertex von P i in dem Algorithmus ist, den ich beschrieben habe, insbesondere derjenige, der S am nächsten ist . Liege ich falsch? riPiS
Domotorp
Dies scheint eine dieser üblichen, aber langwierigen allgemeinen Positionsannahmen zu sein. Wenn Sie sich nicht um die Laufzeit kümmern, können Sie einen Scheitelpunkt vom Grad durch zwei extrem nahe Scheitelpunkte vom Grad d / 2 + 3 ersetzen (wenn Sie auf dreieckigen Flächen bestehen). Wiederholen Sie dies, bis alle Eckpunkte kleiner als 10 sind.dd/2+3
Sariel Har-Peled
@Sariel: Ich dachte das Gleiche, aber warum sollte der Prozess dann enden? Beachten Sie, dass beim Löschen eines Scheitelpunkts dessen Nachbarn möglicherweise keine Fläche bilden. Daher müssen Sie möglicherweise neue Kanten hinzufügen. In der Tat müssen Sie möglicherweise den Grad eines Scheitelpunkts erhöhen.
Domotorp
1

Für den Fall, dass sich noch jemand für die Frage interessiert: Auf den Haken in der Dobkin-Kirpatrick-Erklärung wurde auch in Barbas und Langermans Optimaler Erkennung von Schnittpunkten zwischen konvexen Polyedern hingewiesen .

Sie stellen in der Arbeit (SODA 2015-Version, nicht Arxiv) fest, dass O'Rourkes Computational Geometry in C , Kapitel 7, bereits eine Problemumgehung beschreibt (die im Wesentlichen Sariels Antwort ist). Das SODA-Papier stellt auch eine alternative Lösung vor. Definieren einer Variante der DK-Hierarchie, in der jeder Scheitelpunkt einen begrenzten Grad hat.

Joseph Stack
quelle