18
Dr. Martin N¨ ollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualit¨ at Martin N¨ ollenburg Vorlesung Algorithmische Geometrie INSTITUT F ¨ UR THEORETISCHE INFORMATIK · FAKULT ¨ AT F ¨ UR INFORMATIK Geradenarrangements und Dualit¨ at von Punkten und Geraden 12.06.2012

Vorlesung Algorithmische Geometrie Geradenarrangements …...untere Kontur der von oben begrenzenden Geraden obere Kontur der von unten begrenzenden Geraden Schnitt der beiden konvexen

  • Upload
    others

  • View
    1

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Vorlesung Algorithmische Geometrie Geradenarrangements …...untere Kontur der von oben begrenzenden Geraden obere Kontur der von unten begrenzenden Geraden Schnitt der beiden konvexen

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

Martin Nollenburg

Vorlesung Algorithmische Geometrie

INSTITUT FUR THEORETISCHE INFORMATIK · FAKULTAT FUR INFORMATIK

Geradenarrangements und Dualitat von Punkten und Geraden

12.06.2012

Page 2: Vorlesung Algorithmische Geometrie Geradenarrangements …...untere Kontur der von oben begrenzenden Geraden obere Kontur der von unten begrenzenden Geraden Schnitt der beiden konvexen

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

Dualitatsabbildung

p = (2, 1)

Bisher haben wir Dualitat fur planare Graphen bzw.Voronoi-Diagramme und Delaunay-Triangulierungen gesehen.Auch Punkte und Geraden konnen dual zueinander sein.

p⇤ : b = 2a� 1

x

y

a

b

Def.:p = (p

x

, py

)

Die Dualitatsabbildung (·)⇤ ist definiert durch

` : y = �x+ 1.5

`⇤ = (�1,�1.5)

` : y = mx+ c `⇤ = (m,�c)7!

p⇤ : b = px

a� py

7!

primaleEbene

dualeEbene

Page 3: Vorlesung Algorithmische Geometrie Geradenarrangements …...untere Kontur der von oben begrenzenden Geraden obere Kontur der von unten begrenzenden Geraden Schnitt der beiden konvexen

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

Eigenschaften

Lemma 1: Es gelten die folgenden Eigenschaften

(p⇤)⇤ = p und (`⇤)⇤ = `p liegt unter/auf/uber ` , p⇤ lauft uber/auf/unter `⇤

`1 und `2 schneiden sich in r, r⇤ geht durch `⇤1 und `⇤2q, r, s kollinear, q⇤, r⇤, s⇤ schneiden sich in gemeinsamem Punkt

x

y

a

bp

q

r

s`1

`2

p⇤

q⇤ r⇤

s⇤`⇤1

`⇤2

Page 4: Vorlesung Algorithmische Geometrie Geradenarrangements …...untere Kontur der von oben begrenzenden Geraden obere Kontur der von unten begrenzenden Geraden Schnitt der beiden konvexen

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

Eigenschaften

Lemma 1: Es gelten die folgenden Eigenschaften

(p⇤)⇤ = p und (`⇤)⇤ = `p liegt unter/auf/uber ` , p⇤ lauft uber/auf/unter `⇤

`1 und `2 schneiden sich in r, r⇤ geht durch `⇤1 und `⇤2q, r, s kollinear, q⇤, r⇤, s⇤ schneiden sich in gemeinsamem Punkt

Wie sieht das duale Objekt zu einer Strecke s = pq aus?

Welche duale Beziehung gilt fur eine Gerade `, die s schneidet?

p

q` p⇤ q⇤

s⇤

`⇤

Page 5: Vorlesung Algorithmische Geometrie Geradenarrangements …...untere Kontur der von oben begrenzenden Geraden obere Kontur der von unten begrenzenden Geraden Schnitt der beiden konvexen

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

Anwendungen der Dualitat

Dualitat macht geometrische Probleme weder leichter nochschwerer; sie bietet einen anderen (oft hilfreichen) Blickwinkel!

Wir werden zwei Beispiele genauer betrachten:

untere/obere Konturen von Geradenarrangementskleinstes Dreieck in einer Punktmenge

Page 6: Vorlesung Algorithmische Geometrie Geradenarrangements …...untere Kontur der von oben begrenzenden Geraden obere Kontur der von unten begrenzenden Geraden Schnitt der beiden konvexen

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

Untere Kontur

Def.: Fur eine Menge L von Geraden ist die untere KonturUK(L) von L die Menge aller Punkte aus [

`2L

`, dieunterhalb aller Geraden aus L liegen.

Moglichkeiten zur Berechnung der unteren Kontur:Algorithmus IntersectHalfplanes aus 4. VLBetrachte das duale Problem fur L⇤

= {`⇤ | ` 2 L}

UK(L)

Page 7: Vorlesung Algorithmische Geometrie Geradenarrangements …...untere Kontur der von oben begrenzenden Geraden obere Kontur der von unten begrenzenden Geraden Schnitt der beiden konvexen

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

Kontur und Dualitat

`

p q

Wann erscheint ` als Strecke pq auf UK(L)?

p und q liegen unterhalb aller Geraden in L

p⇤ und q⇤ liegen oberhalb aller Punkte aus L⇤

) liegen benachbart auf oberer konvexer Hulle OKH(L⇤)

Schnittpunkt von p⇤ und q⇤ ist `⇤, Knoten von OKH(L⇤)

p⇤

q⇤`⇤

OKH(L⇤)

Lemma 2:Die Geraden auf UK(L) von rechts nach linksentsprechen den Knoten auf OKH(L⇤

) von linksnach rechts.

`l

`r

`⇤l

`⇤r

Page 8: Vorlesung Algorithmische Geometrie Geradenarrangements …...untere Kontur der von oben begrenzenden Geraden obere Kontur der von unten begrenzenden Geraden Schnitt der beiden konvexen

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

Berechnung der Kontur

Algorithmus zur Berechnung der oberen konvexen Hulle mitLaufzeit O(n log n) (s. erste VL zu konvexer Hulle)

Primale Geraden zu Punkten auf OKH(L⇤) in umgekehrter

Reihenfolge bilden UK(L)

Analog: obere Kontur von L = untere konvexe Hulle von L⇤

Wie lasst sich das nutzen um den Schnittvon n Halbebenen zu berechnen?

untere Kontur der von oben begrenzenden Geradenobere Kontur der von unten begrenzenden GeradenSchnitt der beiden konvexen Regionen (s. 4. VL)insgesamt O(n log n) Laufzeit

Page 9: Vorlesung Algorithmische Geometrie Geradenarrangements …...untere Kontur der von oben begrenzenden Geraden obere Kontur der von unten begrenzenden Geraden Schnitt der beiden konvexen

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

Wie testet man ob n Punkte in allgemeiner Lage sind?

Wie findet man eine maximal große Menge kollinearer Punkte?

Zwischenfrage:

Page 10: Vorlesung Algorithmische Geometrie Geradenarrangements …...untere Kontur der von oben begrenzenden Geraden obere Kontur der von unten begrenzenden Geraden Schnitt der beiden konvexen

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

Geradenarrangements

Def.: Eine Menge L von Geraden definiert eine UnterteilungA(L) der Ebene (das Geradenarrangement) in Knoten,Kanten und Zellen (tlws. unbeschrankt).A(L) heißt einfach, wenn keine drei Geraden durcheinen Punkt gehen und keine zwei Geraden parallel sind.

Kante Knoten

Zelle

Page 11: Vorlesung Algorithmische Geometrie Geradenarrangements …...untere Kontur der von oben begrenzenden Geraden obere Kontur der von unten begrenzenden Geraden Schnitt der beiden konvexen

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

Komplexitat von A(L)

Die kombinatorische Komplexitat von A(L) ist die Zahl derKnoten, Kanten und Zellen. Es gilt:

Satz 1: Sei A(L) ein einfaches Arrangement von n Geraden.Dann hat A(L)

�n

2

�Knoten, n2 Kanten und�

n

2

�+ n+ 1 Zellen.

Datenstruktur fur A(L):

fuge bounding box aller Knoten hinzu (s. Ubung)! planar eingebetteter Graph Gdoppelt-verkettete Kantenliste fur G

Page 12: Vorlesung Algorithmische Geometrie Geradenarrangements …...untere Kontur der von oben begrenzenden Geraden obere Kontur der von unten begrenzenden Geraden Schnitt der beiden konvexen

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

Konstruktion von A(L)

Input: Geraden L = {`1, . . . , `n}Output: DCEL D fur A(L)initialisiere D fur bounding box B der Knoten von A(L)for i 1 to n do

finde linkesten Schnittpunkt von `i

mit Kante e von Bf innere Zelle inzident zu ewhile f 6= außere Zelle do

zerteile f , update D und setze f auf nachste Zelle

e

Laufzeit?

Startpunkt `i

: O(i)

while-Schleife:O(|roter Pfad|)

bounding box: O(n2)

Page 13: Vorlesung Algorithmische Geometrie Geradenarrangements …...untere Kontur der von oben begrenzenden Geraden obere Kontur der von unten begrenzenden Geraden Schnitt der beiden konvexen

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

Zonensatz

Def.: Fur ein Arrangement A(L) und eine Gerade ` 62 L ist dieZone ZA(`) die Menge aller Zellen von A(L), derenAbschluss ` schneidet.

Wie viele Zellenenthalt ZA(`)?

Wie viele Kantenenthalt ZA(`)?

Satz 2: Fur ein Arrangement A(L) von n Geraden in derEbene und eine Gerade ` 62 L besteht ZA(`) aushochstens 10n Kanten.

Satz 3: Das Arrangement A(L) einer Menge von n Geradenkann in O(n2

) Zeit und Platz konstruiert werden.

linkeGrenzkante

rechteGrenzkanten ZA(`)

Page 14: Vorlesung Algorithmische Geometrie Geradenarrangements …...untere Kontur der von oben begrenzenden Geraden obere Kontur der von unten begrenzenden Geraden Schnitt der beiden konvexen

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

Wie testet man ob n Punkte in allgemeiner Lage sind?

Wie findet man eine maximal große Menge kollinearer Punkte?

Zwischenfrage:

Page 15: Vorlesung Algorithmische Geometrie Geradenarrangements …...untere Kontur der von oben begrenzenden Geraden obere Kontur der von unten begrenzenden Geraden Schnitt der beiden konvexen

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

Kleinstes Dreieck

Gegeben eine Menge P von n Punkten in R2, finde einflachenminimales Dreieck �pqr mit p, q, r 2 P .

Seien p, q 2 P . Der Punkt r 2 P \ {p, q}, der �pqr minimiert,liegt auf dem Rand des großten leeren Korridors entlang pq.

pqr

Zwischen pq und der Geraden `r

durch r parallel zu pq liegtkein weiterer Punkt aus P .

`r

Im Dualen: `⇤r

liegt auf r⇤

`⇤r

und (pq)⇤ haben gleiche x-Koordinatekeine Gerade p⇤ 2 P ⇤ schneidet `⇤

r

(pq)⇤

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

(pq)⇤

`⇤r

r⇤

q⇤

p⇤

Page 16: Vorlesung Algorithmische Geometrie Geradenarrangements …...untere Kontur der von oben begrenzenden Geraden obere Kontur der von unten begrenzenden Geraden Schnitt der beiden konvexen

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

Berechnung im Dualen

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

(pq)⇤

`⇤r

r⇤

q⇤

p⇤

`⇤r

liegt vertikal uber oder unter (pq)⇤ in einergemeinsamen Zelle von A(P ⇤

) ) nur zwei Kandidaten

Berechne in O(n2) Zeit das Arrangement A(P ⇤

)

Berechne in jeder Zelle die vertikalen Nachbarn der Knoten! Zeit linear in Zellenkomplexitat

fur alle O(n2) Kandidaten-Tripel (pq)⇤r⇤ berechne in O(1)

Zeit Flache �pqr

findet Minimum in insgesamt O(n2) Zeit

wie?

pqr

`r

Page 17: Vorlesung Algorithmische Geometrie Geradenarrangements …...untere Kontur der von oben begrenzenden Geraden obere Kontur der von unten begrenzenden Geraden Schnitt der beiden konvexen

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

Weitere Probleme

Gegeben n Strecken in der Ebene, finde eine maximalestabbing-Gerade, d.h. eine Gerade, die moglichst vieleStrecken schneidet.

Zwei Diebe haben eine Kette aus Diamanten undSmaragden gestohlen und mochten Sie teilen, ohne sie zusehr zu zerstoren. Wieviele Schnitte sind notig?

Satz 4: Seien S,D zwei endliche Punktmengen in der Ebene.Dann gibt es eine Gerade `, die gleichzeitig S und Dhalbiert.

Page 18: Vorlesung Algorithmische Geometrie Geradenarrangements …...untere Kontur der von oben begrenzenden Geraden obere Kontur der von unten begrenzenden Geraden Schnitt der beiden konvexen

Dr. Martin Nollenburg · Vorlesung Algorithmische Geometrie Geradenarrangements und Dualitat

Diskussion

Dualitat ist ein sehr nutzliches Werkzeug in der algorithmischenGeometrie!

Ja, auch zwischen d-dimensionalen Punkten und Hyperebenen gibt eseine entsprechende inzidenz- und ordnungserhaltende Dualitatsabbildung.

Kann man die Dualitat auch in hoheren Dimensionen nutzen?

Wie steht es um hoherdimensionale Arrangements?

Das Arrangement von n Hyperebenen im Rd hat Komplexitat ⇥(nd

).Eine Verallgemeinerung des Zonensatzes fuhrt zu einem O(nd

)-ZeitAlgorithmus.