Testen, ob eine Menge von n Punkten in der Ebene in o (nlogn) Zeit ein konvexes n Polygon bildet

Angenommen, Sie erhalten eine Menge von n Punkten in der Ebene und möchten prüfen, ob sie ein konvexes n-Polygon bilden, dh ob sie alle auf der konvexen Hülle liegen. Ich habe mich gefragt, ob irgendjemand weiß, wie man das in o (nlogn) Zeit macht, dh ohne den CH zu berechnen.

cg.comp-geom Babis Tsourakakis
quelle

Sie können die konvexe Hülle in O (n log n) Zeit berechnen. Meinen Sie, wenn es möglich ist, es in kürzerer Zeit zu tun ?

Per Vognsen

Ja, ich glaube, dass es für dieses Problem einen linearen Zeitalgorithmus geben sollte. aber ich weiß nicht wie

Babis Tsourakakis

Er schrieb o (nlogn) nicht O (nlogn), also ist seine Frage richtig.

Shiva Kintali

Ich benutze die kleine o-Notation, damit die Frage immer noch so bleibt, wie sie ist

Babis Tsourakakis

Es macht mich ein bisschen unruhig, wenn ich sehe, dass die Sortierung von Zahlen (oder äquivalent konvexen Hüllen von kartesischen Punkten) Θ (n log n) Zeit in Anspruch nimmt, ohne dass explizit angegeben wird, welches Berechnungsmodell Sie verwenden. Die Vergleichssortierung dauert Θ (n log n), aber das Vergleichsmodell erlaubt nicht einmal die Berechnung von Rümpfen. Beide haben noch Θ (n log n) Zeit für algebraische Entscheidungsbäume (wie die akzeptierte Antwort zeigt), sind jedoch in Berechnungsmodellen, die tatsächlichen Computern ähnlicher sind, schneller.

David Eppstein

Antworten:

Das scheint zumindest in den Vergleichs / Algebraischen Baummodellen unwahrscheinlich. Definition zuerst:

Eine Punktmenge befindet sich in konvexer Position, wenn kein Punkt von als konvexe Kombination der verbleibenden Punkte von . $P$ $P$ $P$

Die Entscheidung, ob eine Menge von Zahlen alle verschieden sind, dauert (dies ist als EINZIGARTIGKEIT bekannt). Wenn eine solche Menge von Zahlen , ordne sie der Menge von Punkten Wenn es keine wiederholte Zahl gibt, befinden sich die Punkte in konvexer Position. $n$ $\Omega(n \log n)$ $n$ $X$

P = {(x, x^{2}) | x \in X} .

$P = \{ (x, x^2) | x \in X\}.$

Wenn es eine wiederholte Nummer gibt, entspricht diese wiederholte Nummer einem Punkt, der als konvexe Kombination der verbleibenden Punkte geschrieben werden kann. Die Punkte befinden sich nämlich nicht in einer konvexen Position.

Die Entscheidung, ob sich ein Punktsatz in einer konvexen Position befindet, ist so schwer wie EINZIGARTIG.

Sariel Har-Peled
quelle

X [i]

$X[i]$

(X [i], X [i]^{2} + i / n^{2})

$(X[i], X[i]^2+i/n^2)$

@Babis: Jeffs Reduktion funktioniert, wenn doppelte Punkte nicht erlaubt sind. Die durch die Reduzierung erzeugten Punkte sind unabhängig von der ursprünglichen Anordnung eindeutig.

Vinayak Pathak

Wir erhalten also, dass die Anzahl der Ecken der konvexen Hülle genau dann gleich n ist, wenn keine zwei Punkte die gleiche x-Koordinate haben. Vielen Dank, anfangs dachte ich, dass es einfacher sein sollte als zu sortieren.

Babis Tsourakakis

Dank Vinayak hatte ich Jeffs Reduktion nicht gesehen, da sie zur selben Zeit veröffentlicht wurde, als ich den vorherigen Kommentar schrieb, den ich durch den obigen

ersetzte

Klar, ich bin nicht einverstanden mit dem Satz "Standardmodell". Genau das ist der Word-RAM :) Es ist das Modell, das einem echten Computer am ehesten entspricht und das wir zum Analysieren von Algorithmen in den meisten TCS verwenden. Geometrie hat eine Ausnahme für die Verwendung des Real RAM geltend gemacht, damit wir uns nicht mit Präzisionsproblemen befassen müssen. Aber das ist nicht "das Standardmodell".

Mihai

-1

$O(n log n)$

Sobald Sie die Reihenfolge der Punkte kennen, sollte der Winkel von jedem Punkt zum nächsten Punkt in der Sequenz monoton sein. Dies ist eine notwendige und meines Erachtens ausreichende Voraussetzung.

Das Erhalten des inneren Punktes wird dem Leser als Übung überlassen.

$O(n log n)$

BCS
quelle

Sie haben sein o (n log n) wahrscheinlich genauso falsch interpretiert wie O (n log n) wie ich. Wie auch immer, der Algorithmus, den Sie umrissen haben, ist die Geschenkverpackung in embryonaler Form. Sie müssen keinen inneren Punkt verwenden. Sie können einen Punkt an der Grenze verwenden, z. B. einen Punkt mit einer minimalen x-Koordinate.

Per Vognsen,

@Per Vognsen: Mein Algo, muss noch die Punkte sortieren, damit es nur geht

O (n l o g n)

$O(n log n)$ (Übrigens ist

o ()

$o()$ eine exklusive Grenze?)

BCS

Der Punkt ist, dass es viele konvexe Rumpfalgorithmen gibt, die in O (n log n) ausgeführt werden. Ihr Algorithmus ist im Grunde eine einfache alte Geschenkverpackung. Er bat um etwas schnelleres, zB lineare Zeit. Siehe die anderen Antworten.

Per Vognsen

Wenn Sie sich die akzeptierte Antwort über Ihrer Bearbeitung ansehen, werden Sie feststellen, dass das Problem der Eindeutigkeit von Elementen entspricht, die eine untere Grenze von O (n log n) haben.

Per Vognsen

@BCS: Ich fürchte, Sie haben ein Missverständnis bezüglich der Antwort von Sariel Har-Peled. Die Reduzierung erfolgt von der Eindeutigkeit zur Prüfung der konvexen Position, nicht in die andere Richtung. Das heißt, Sariel (und JeffE) gaben an, dass Sie, wenn Sie eine Reihe von Zahlen erhalten und die Eindeutigkeit testen möchten, diese in eine Reihe von Punkten umwandeln und einen beliebigen Algorithmus für das Testen der konvexen Position verwenden können.

Tsuyoshi Ito