Computing shortest transversals

Binay Bhattacharya, Godfried Toussaint

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 18th International Colloquium, Proceedings
EditorsJavier Leach Albert, Mario Rodriguez Artalejo, Burkhard Monien
PublisherSpringer Verlag
Pages649-660
Number of pages12
ISBN (Print)9783540542339
DOIs
StatePublished - 1991
Event18th International Colloqulum on Automata, Languages, and Programming, ICALP 1991 - Madrid, Spain
Duration: Jul 8 1991Jul 12 1991

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume510 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other18th International Colloqulum on Automata, Languages, and Programming, ICALP 1991
CountrySpain
CityMadrid
Period7/8/917/12/91

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Computing shortest transversals'. Together they form a unique fingerprint.

  • Cite this

    Bhattacharya, B., & Toussaint, G. (1991). Computing shortest transversals. In J. L. Albert, M. R. Artalejo, & B. Monien (Eds.), Automata, Languages and Programming - 18th International Colloquium, Proceedings (pp. 649-660). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 510 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-54233-7_171