TY - GEN
T1 - Computing shortest transversals
AU - Bhattacharya, Binay
AU - Toussaint, Godfried
N1 - Funding Information:
The research reported here was supported by the Natural Sciences & Engineering Research Council of Canada, FCAR in Quebec, and the British Columbia Advanced Systems Institute. The research was carried out while the second author was an Advanced Systems Institute Fellow at Simon Fraser University during the fall of 1988. The authors are grateful to David Dobkin, David Kirkpatrick, Victor Klee and Slawomir Pilarski for fruitful discussions on this topic. Finally we thank an anonimous referee for providing an elegant proof that l(x) in lemma 2.1 is in fact a convex function.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1991.
PY - 1991
Y1 - 1991
N2 - We present an 0(n log2 n) time and 0(n) space algorithm for computing the shortest line segment that intersects a set of n given line segments or lines in the plane. If the line segments do not intersect the algorithm may be trimmed to run in O(n log n) time. Furthermore, in combination with linear programming the algorithm will also find the shortest line segment that intersects a set of n isothetic rectangles in the plane in 0(n log k) time, where k is the combinatorial complexity of the space of transversals and k ≤ 4n. These results find application in: (1) line-fitting between a set of n data ranges where it is desired to obtain the shortest line-of-fit, (2) finding the shortest line segment from which a convex n-vertex polygon is weakly externally visible, and (3) determining the shortest line-of-sight between two edges of a simple n-vertex polygon, for which 0(n) time algorithms are also given. AU 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.
AB - We present an 0(n log2 n) time and 0(n) space algorithm for computing the shortest line segment that intersects a set of n given line segments or lines in the plane. If the line segments do not intersect the algorithm may be trimmed to run in O(n log n) time. Furthermore, in combination with linear programming the algorithm will also find the shortest line segment that intersects a set of n isothetic rectangles in the plane in 0(n log k) time, where k is the combinatorial complexity of the space of transversals and k ≤ 4n. These results find application in: (1) line-fitting between a set of n data ranges where it is desired to obtain the shortest line-of-fit, (2) finding the shortest line segment from which a convex n-vertex polygon is weakly externally visible, and (3) determining the shortest line-of-sight between two edges of a simple n-vertex polygon, for which 0(n) time algorithms are also given. AU 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.
UR - http://www.scopus.com/inward/record.url?scp=69949154918&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=69949154918&partnerID=8YFLogxK
U2 - 10.1007/3-540-54233-7_171
DO - 10.1007/3-540-54233-7_171
M3 - Conference contribution
AN - SCOPUS:69949154918
SN - 9783540542339
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 649
EP - 660
BT - Automata, Languages and Programming - 18th International Colloquium, Proceedings
A2 - Albert, Javier Leach
A2 - Artalejo, Mario Rodriguez
A2 - Monien, Burkhard
PB - Springer Verlag
T2 - 18th International Colloqulum on Automata, Languages, and Programming, ICALP 1991
Y2 - 8 July 1991 through 12 July 1991
ER -