ISSN:
1436-5057
Keywords:
52.A30
;
52.A10
;
transversals
;
stabbing lines
;
algorithms
;
complexity
;
computational geometry
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Wir stellen einen Algorithmus zur Berechnung der kürzesten Strecke vor, welchen in der Ebene gegebene Geraden oder Strecken schneidet. Die Berechnung erfordertO(nlog2 n) Zeit undO(n) Platz. Falls sich die Strecken nicht schneiden, kann der Zeitbedarf aufO(nlogn) reduziert werden. In Verbindung mit Linearer Optimierung findet der Algorithmus auch die kürzeste Strecke, welchen isothetische Rechtecke schneidet. Hier ist der ZeitbedarfO(nlogk), wobeik die kombinatorische Komplexität des Raumes der Transversalen ist undk≤4n gelten muß. Mögliche Anwendungen der Ergebnisse sind: (1) Bestimmung der kürzestenPass-Linie fürn Datenbereiche, (2) Bestimmung der kürzesten Strecke, von welcher ein konvexesn-Polygon schwach sichtbar ist und (3) Bestimmung der kürzestenSichtlinie eines einfachenn-Polygons, wobei wir auchO(n)-Zeit Algorithmen angeben. Alle Algorithmen beruhen auf der Lösung einer grundlegenden geometrischen Optimierungsaufgabe. Diese ist von selbständigem Interesse und sollte weitere Anwendungen ermöglichen.
Notes:
Abstract We present anO(nlog2 n) time andO(n) space algorithm for computing the shortest line segment that intersects a set ofn given line segments or lines in the plane. If the line segments do not intersect the algorithm may be trimmed to run inO(nlogn) time. Furthermore, in combination with linear programming the algorithm will also find the shortest line segment that intersects a set ofn isothetic rectangles in the plane inO(nlogk) time, wherek is the combinatorial complexity of the space of transversals andk≤4n. These results find application in: (1) line-fitting between a set ofn data ranges where it is desired to obtain the shortestline-of-fit, (2) finding the shortest line segment from which a convexn-vertex polygon is weakly externally visible, and (3) determing the shortestline-of-sight between two edges of a simplen-vertex polygon, for whichO(n) time algorithms are also given. All the algorithms are based on the solution to a new fundamental geometric optimization problem that is of independent interest and should find application in different contexts as well.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02239165
