Transformationen

Untere Schranke für die Berechnung der konvexen Hülle

 aufwärts

Problem

Gegeben ist eine endliche Menge von n Punkten in der Ebene, gesucht ist die konvexe Hülle dieser Punkte. Dies ist der kürzeste konvexe Polygonzug, der diese Punkte umschließt (Bild 1).

Bild 1: Endliche Menge von Punkten (a) und konvexe Hülle der Punkte (b)
Bild 1: Endliche Menge von Punkten (a) und konvexe Hülle der Punkte (b)

Transformation

Es wird gezeigt, dass die Berechnung der konvexen Hülle von n Punkten mindestens so schwer ist wie das Sortieren von n ver­schiedenen Zahlen.

Hierzu wird das Sortier­problem auf das Problem der Berechnung der konvexen Hülle reduziert. Dies geschieht in drei Schritten:

 

Bild 2 zeigt schematisch dieses Vorgehen.

Bild 2: Transformationsschema
Bild 2: Transformationsschema

Gegeben sei also ein beliebiger Fall des Sortier­problems mit n ver­schiedenen Zahlen x0, ..., xn-1.

Die Trans­formation besteht darin, dass zu jeder dieser Zahlen xi der Punkt (xi, xi2) erzeugt wird.

Diese n Punkte liegen auf der Normal­parabel (Bild 3). Die konvexe Hülle dieser Punktmenge besteht aus diesen Punkten selber, d.h. alle sind Eckpunkte des konvexen Hüllpolygons. Das Ergebnis der Berechnung der konvexen Hülle sind die n Eckpunkte in umlaufender Reihenfolge.

Aus dieser Lösung des Konvexe-Hülle-Problems ergibt sich die Lösung des Sortier­problems, indem zunächst der Eckpunkt mit kleinster x-Koordinate gesucht wird und von diesem aus die x-Koordinaten der Eckpunkte in umlaufender Reihenfolge ausgegeben werden. Die Folge dieser x-Koordinaten ist die sortierte Folge x0, ..., xn-1.

Konvexe Hülle von Punkten auf der Parabel
Bild 3: Konvexe Hülle der Punktemenge { (xi, xi2) }

Die Trans­formation, nämlich das Erzeugen der n Punkte aus den n Zahlen, benötigt Zeit O(n). Die Rück­trans­formation, nämlich das Suchen des Punktes mit kleinster x-Koordinate, benötigt ebenfalls Zeit O(n). Somit muss die Berechnung der konvexen Hülle Zeit Ω(n log(n)) benötigen. Denn ginge es schneller, so könnten wir schneller als in Zeit Ω(n log(n)) sortieren. Dies aber ist nicht möglich, da Ω(n log(n)) eine untere Schranke für das Sortier­problem ist.

Satz:  Die Zeit­komplexität des Problems der Berechnung der konvexen Hülle von n Punkten liegt in Ω(n log(n)).

Algorithmen zur Berechnung der konvexen Hülle mit einer Zeit­komplexität von O(n log n) sind also optimal, so z.B. der Graham-Scan-Algorithmus.

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 25.12.2002   Updated: 05.06.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik