Effiziente Algorithmen 2002
P-35

Geben Sie einen Algorithmus an, der alle Ueberschneidungen in einer
Menge von n Strecken in Zeit O((n+k) log n) findet, wobei k die Anzahl
der Ueberschneidungen ist.


Vereinfachende Annahmen:
- keine Strecke ist vertikal,
- keine drei Strecken schneiden sich in einem Punkt,
- kein zwei Strecken ueberlappen sich.


Ereignisse
----------

Wir betrachten folgende Ereignisse e.

Start(a,p)     p ist Startpunkt der Strecke a
End(a,p)       p ist Endpunkt der Strecke a
Inter(a,b,p)   p ist Schnittpunkt der Strecken a, b, wobei links von p
	       a unterhalb von b liegt und rechts von p oberhalb.

Diese Ereignisse werden in einer Queue verwaltet, lexikographisch nach
den Koordinaten (x,y) von p sortiert.
Die Queue unterstuetzt folgende Operationen und kann durch einen Heap
realisiert werden.

Zeit O()  Operation  Beschreibung
--------  ---------  ------------
log n	  PUSH(e)    sortiert e in die Queue ein, falls es sich noch
                     nicht in der Schlange befindet
		     (entspricht HEAP-INSERT(e))
log n	  POP()      gibt das erste Element in der Schlange zurueck
		     und entfernt dieses
		     (entspricht HEAP-EXTRACT-MIN())
1         EMPTY()    gibt true zurueck, wenn die Schlange leer ist,
                     sonst false.

Zu Beginn werden fuer jede der gegebenen Strecken die Ereignisse Start
und End in die Queue eingefuegt => Zeit O(n log n).

Die Laenge der Queue ist stets maximal 2n + k.  Das aendert aber nichts
and er Komplexitaet, da die Anzahl der Schnittpunkte k beschraenkt ist
durch n^2 und ausserdem O(log(n^2)) = O(2 log n) = O(log n).


Ordnung
-------

Wir verwenden die in der Vorlesung vorgestellte Datenstruktur, die
eine partielle Ordnung auf den Strecken verwaltet.  Realisiert wird
die Datenstruktur durch irgendeinen geordneten, balancierten Suchbaum.
Die Ordung enthaelt maximal jede Strecke einmal.  Deshalb ist die
Tiefe des Suchbaums beschraenkt durch log n.

Zeit O()  Operation    Beschreibung
--------  ---------    ------------
log n	  INSERT(a,x)  Fuegt Strecke a in die Ordnung kein, wobei der
		       Strahl sich auf Koordinate x befindet.
log n	  DELETE(a)    Loescht Strecke a aus der Ordnung.
log n	  ABOVE(a)     Nachfolger von a in der Ordnung.
log n	  BELOW(a)     Vorgaenger von a in der Ordunung.
log n	  SWAP(a,b)    Vertauschen von a und b in der Ordung.
		       Dabei sind a und b Nachbarn, d.h. vor
                       Ausfuehrung ist b = ABOVE(a) und a = BELOW(b).


Weitere Operationen
-------------------

Zeit O()  Operation    Beschreibung
--------  ---------    ------------
1	  OUTPUT(p)    Gibt den gefundenen Schnittpunkt p aus.
1	  ISECT(a,b)   Gibt den Schnittpunkt p von a und b zurueck,
		       NIL, falls keiner existiert.


Invariante
----------

Alle Schnittpunkte links vom Strahl x sind bereits ausgegeben worden.
Solche, die sich rechts vom Strahl befinden und von Nachbarn in der
Ordnung herruehren, sind als Ereignisse in die Queue eingefuegt.

Neue Schnittpunkte koennen sich nur ergeben, falls sich in der
Ordnungsstruktur die Nachbarschaftsverhaeltnisse aendern.  Diese
koennen durch folgende Ereignisse hervorgerufen werden.

INSERT(a,x)   Danach koennen sich Schnittpunkte von a mit ABOVE(a) und
              BELOW(a) ergeben.

DELETE(a)     Die Strecken, die vor DELELE(a) die Nachbarn von a
              waren, werden nun Nachbarn zueinander und koennen sich
              schneiden.

SWAP(a,b)     Mit b=ABOVE(a). Nach dieser Operation kann sich a mit
              ABOVE(a) und b mit BELOW(b) schneiden.	      	

Werden alle diese Schnittmoeglichkeiten behandelt, ist die Invariante
nach einer Operation auf der Ordnung wiederhergestellt.


Subroutine TRY-ISECT(a,b)
-------------------------

Diese Routine berechnet den Schnittpunkt p von a und b.  Dabei ist
b oberhalb von a an der derzeitigen Strahlposition.
Falls er existiert, wird er ausgegeben und als neues Ereignis in die Queue
eingefuegt.  Gemaess Invariante liegt er rechts der Strahlposition x.

Zeit O()  TRY-ISECT(a,b)
--------  --------------
1	  1 p = ISECT(a,b)
log n     2 if p != NIL then PUSH(Inter(a,b,p))


Algorithmus ALL-ISECT
---------------------

Der Algorithmus gibt alle Schnittpunkte aus, sortiert nach x-Koordinate.

Zeit O()  ALL-ISECT(a,b)
--------  --------------
n log n	  01 Sortiere die Strecken in die Queue ein
1         02 while not EMPTY() do  
1         03   case POP() of 
1         04     Start(a,(x,y)) =>
log n     05       INSERT(a,x)
log n     06       TRY-ISECT(a,ABOVE(a)) 
log n     07       TRY-ISECT(BELOW(a),a)
1         08     End(a,(x,y)) =>
log n     09       TRY-ISECT(BELOW(a),ABOVE(a)) 
log n     10       DELETE(a)
1         11     Inter(a,b,p) =>
1         12       OUTPUT(p)
log n     13       SWAP(a,b)
log n     14       TRY-ISECT(BELOW(b),b)
log n     15       TRY-ISECT(a,ABOVE(a))

Die Schleife wird sooft durchlaufen, wie es Ereignisse gibt.  Es gibt
n Ereignisse Start, n Ereignisse End und k Ereignisse Inter.  Jeder
Durchlauf benoetigt O(log n) Zeit.

==> Gesamt-Zeit O((n+k) log n).


Andreas Abel