Randomisierter Minidisc Algorithmus in O(n)


Gegeben: n Punkte in Euklidischer Ebene
Gesucht: kleinerster Kreis, der alle Punkte enthält
Der Algorithmus funktioniert wie folgend:
 
Zunächst bestimme Permutation aller Punkte.
Finde Minidisc der zwei ersten Punkte (trivial).
Für alle Punkte 1..n ist
      entweder pi schon in der aktuellen Minidisc enthalten oder
      er muss auf dem Rand einer MD liegen, der alle bisherigen Punkte
      enthält -> Rufe MD1P({p1,...,pi-1},pi) auf.

MD1P(P',fester Punkt p)

Zunächst bestimme Permutation aller Punkte aus P'.
Finde Minidisc von p1 und p.
Für alle Punkte aus P': p2..pn ist
      entweder pi schon in der aktuellen Minidisc enthalten oder
      er muss auf dem Rand einer MD liegen, der alle bisherigen Punkte
      enthält und auf deren Rand p liegt -> Rufe MD2P({p1,...,pi-1},pi,q) auf.

MD2P(P'',feste Punkte p,p')

Zunächst bestimme Permutation aller Punkte aus P''.
Finde Minidisc von p und p'.
Für alle Punkte aus P'': p1..pn ist
      entweder pi schon in der aktuellen Minidisc enthalten oder
      die MD ist definiert durch pi,p,p'.
Den Algorithmus kann man gleich anhand eines Applets nachvollziehen: