ISSN:
1436-5057
Keywords:
68U05
;
90C25
;
Shortest polygonal paths
;
shortest inpolygons
;
funnel
;
linear time algorithm
;
constrained paths
;
convex function
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Ein klassisches Problem der Geometrie fragt nach einem einbeschriebenen Polygon kürzesten Umfanges eines gegebenen konvexen Polygons. Wir verallgemeinern dieses Problem auf beliebige Polygonzüge im Raum und untersuchen zwei Fälle: im “offenen” Fall kann der gesuchte Streckenzug kürzester Länge einen unterschiedlichen Anfangs- und Endpunkt haben, während im “geschlossenen” Fall diese beiden Punkte zusammenfallen müssen. Es wird gezeigt, daß solche kürzesten Polygonzüge durch kürzeste Streckenzüge in einem ebenen “Kanal” bestimmt werden, die in beiden Fällen durch einen Algorithmus mit linearer Laufzeit bestimmt werden können. Ferner wird der Fall behandelt, daß der gesuchte Polygonzug ohne Knick durch einen vorgegebenen Punkt gehen soll. Es wird gezeigt, daß die Länge des Polygonzuges dann eine streng konvexe Funktion eines bestimmten Winkels ist, wodurch es möglich wird, auch dieses Problem effizient zu lösen.
Notes:
Abstract A classical problem of geometry is the following: given a convex polygon in the plane, find an inscribed polygon of shortest circumference. In this paper we generalize this problem to arbitrary polygonal paths in space and consider two cases: in the “open” case the wanted path of shortest length can have different start and end point, whereas in the “closed” case these two points must coincide. We show that finding such shortest paths can be reduced to finding a shortest path in a planar “channel”. The latter problem can be solved by an algorithm of linear-time complexity in the open as well in the closed case. Finally, we deal with constrained problems where the wanted path has to fulfill additional properties; in particular, if it has to pass straight through a further point, we show that the length of such a constrained polygonal path is a strictly convex function of some angle α, and we derive an algorithm for determining such constrained polygonal paths efficiently.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02250584
Permalink
