Trennung eines vorverarbeiteten Polyeders und einer Ebene

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 $P_{i}$ und $S$ , die durch $r_i$ und verwirklicht wird $s_i$ , die beste Trennung von $P_{i-1}$ und $S$ in $O(1)$ -Schritten finden können. Dies geschieht auf folgende Weise. Wir nehmen die Ebene parallel zu $S$ durch $r_i$ und schneiden $P_{i-1}$ in zwei Teile. Auf der einen Seite, der nächste Punkt zu $S$ ist , $r_i$ und 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 $r_i$ in $P_{i-1}$ 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.

ds.algorithms cg.comp-geom 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:

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$ . Angenommen, Sie möchten den Punkt auf , der einem Abfragepunkt am nächsten liegt. Der grundlegende Algorithmus beginnt mit der Berechnung des nächstgelegenen Punkts zu auf , dann werden alle neuen Bereiche (Zelte) neben berücksichtigtund der nächstgelegene Punkt zu $P_1 \subseteq P_2 \subseteq \ldots \subseteq P_k = P$ $P$ $q$ $c_1$ $q$ $P_1$ $c_1$ $c_2$ $q$ in diesen neuen Regionen, und fahren Sie auf diese Weise fort, bis wir . $P_k$

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 von eine konstante Zeit. $c_i$ $c_{i+1}$ $C_i$

Das Problem ist also, wenn auf einem Scheitelpunkt hohen Grades liegt, weil dann die Anzahl neuer Zelte daneben, wenn nach $c_i$ 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 auf einem Scheitelpunkt, zwei aufeinanderfolgende Kanten erinnern, diebenachbart sind, so dass der nächste Punkt zuin $P_{i+1}$ $c_i$ $v$ $e_i, e_i'$ $v$ $q$ $P_{i+1}$ liegt 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 eine Tangentenrichtung . Lassen das konvexe Vieleck sein , dass der Scheitelpunkt der Figur ist für das Polygon (mit der Ebene definieren , die Scheitel Figur hat in der Richtung der normalen ). Konzeptionell, $v$ $P$ $t_v$ $Q_i(v)$ $v$ $P_i$ $t_v$ $Q_1(v), Q_2(v), ..., Q_k(v)$ Verhält sich wie eine 2D-DK-Hierarchie. Liegt der nächste Punkt auf zu auf einem Scheitelpunkt so entspricht dies und einer benachbarten Kante in , wobei die Kante die Ebene der Scheitelpunktfigur bei schneidet . Wenn der nächste Punkt von zu auf einer Kante , erinnern Sie sich an die beiden benachbarten Kanten von , die die beiden Ecken von (hier) $Q_i(v)$ $q$ $w$ $v$ $e$ $P_i$ $e$ $w$ $Q_i(v)$ $q$ $e'$ $P_i$ $e'$ gehört zu ). $e'$ $Q_i(v)$

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

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

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

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

begrenzt ist. Wenn Sie beispielsweise ein Polyeder haben, bei dem zwei Eckpunkte mit jedem Eckpunkt verbunden sind, wie können Sie dann beginnen?

P_{i - 1} ∖ P_{i}

$P_{i-1}\setminus P_i$

r_{i}

$r_i$

Domotorp

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

aber kein Scheitelpunkt von

r_{i}

$r_i$

P_{i - 1}

$P_{i-1}$

P_{i}

$P_i$

Jeffs

Da ist also das Missverständnis. Ich denke, dass

ein Vertex von

in dem Algorithmus ist, den ich beschrieben habe, insbesondere derjenige, der

am nächsten ist . Liege ich falsch?

r_{i}

$r_i$

P_{i}

$P_i$

S

$S$

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

ersetzen (wenn Sie auf dreieckigen Flächen bestehen). Wiederholen Sie dies, bis alle Eckpunkte kleiner als 10 sind.

d

$d$

d / 2 + 3

$d/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

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