ISSN:
1436-5057
Schlagwort(e):
68U05
;
68C25
;
Polygon
;
geodesics
;
diameter
;
furthest neighbour
;
algorithm
;
complexity
;
computational geometry
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
Beschreibung / Inhaltsverzeichnis:
Zusammenfassung Gegeben sei ein einfaches PolygonP mitn Ecken. Wir geben einen Algorithmus an, der ein Punktepaar auf der Begrenzung vonP liefert, welches die Länge des kürzesten Weges maximiert, der im Äußeren des Polygons verläuft. Den Weg bezeichnen wir als den äußeren geodätischen Durchmesser vonP. Unser Algorithmus benötigt 0(n 2) Zeit und erfordert 0(n) Speicherplatz. Zu unserer Überraschung ist das Problem von dem, der Berechnung des inneren geodätischen Durchmessers vonP völlig verschieden. Während der innere Durchmesser immer in Ecken vonP endet, muß dies für den äußeren Durchmesser nicht der Fall sein. Schließlich zeigen wir noch, daß der Algorithmus so erweitert werden kann, daß er das Problem der entferntesten äußeren geodätischen Nachbarn löst.
Notizen:
Abstract Given a simple polygonP ofn vertices, we present an algorithm that finds the pair of points on the boundary ofP that maximizes theexternal shortest path between them. This path is defined as theexternal geodesic diameter ofP. The algorithm takes0(n 2) time and requires0(n) space. Surprisingly, this problem is quite different from that of computing theinternal geodesic diameter ofP. While the internal diameter is determined by a pair of vertices ofP, this is not the case for the external diameter. Finally, we show how this algorithm can be extended to solve theall external geodesic furthest neighbours problem.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF02247961
Permalink
