Punkte mit unbeschränkten Regionen

Angenommen, diese Punkte sind Nägel, die aus der Zeichenebene hervorstehen. Umspannt man sie mit einem Gummiband, so entsteht ein konvexes Polygon, die konvexe Hülle der Punktmenge. Dies ist die kleinste konvexe Menge, in der alle Punkte enthalten sind.

Manche Punkte liegen im Inneren der konvexen Hülle, andere auf dem Rand. Das sind gerade die Nägel, an denen das Gummiband anliegt.

Im Voronoi-Diagramm sind es nun genau die Punkte auf dem Rand der konvexen Hülle, deren Voronoi-Regionen unbeschränkt sind.

Man kann das schön erkennen, wenn man einen der Punkte zwischen den anderen hindurch verschiebt und dabei seine Region beobachtet.

Probieren Sie es ruhig selbst einmal aus, mit dem VoroGlide-Applet auf dieser Seite.