Computing shortest transversals of sets

Binay Bhattacharya; Jurek Czyzowicz; Peter Egyed; Ivan Stojmenovic; Godfried Toussaint; Jorge Urrutia

doi:10.1145/109648.109656

Computing shortest transversals of sets

Binay Bhattacharya, Jurek Czyzowicz, Peter Egyed, Ivan Stojmenovic, Godfried Toussaint, Jorge Urrutia

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Given a family of objects in the plane, the line transversal problem is to compute a line that intersects every member of the family. In this paper we examine a variation of the line transversal problem that involves computing a shortest line segment that intersects every member of the family. In particular, we give O(nlogn) time algorithms for computing a shortest transversal of a family of n lines and of a family of n line segments. We also present an O(n log² n) time algorithm for computing a shortest transversal of a family of polygons with a total of n vertices. In general, finding a line transversal for a family of n objects takes Ω(n log n) time. This time bound holds for a family of n line segments thus our shortest transversal algorithm for this family is optimal.

Original language	English (US)
Title of host publication	Proceedings of the Annual Symposium on Computational Geometry
Publisher	Association for Computing Machinery
Pages	71-80
Number of pages	10
ISBN (Print)	0897914260
DOIs	https://doi.org/10.1145/109648.109656
State	Published - Jun 1 1991
Event	7th Annual Symposium on Computational Geometry, SCG 1991 - North Conway, United States Duration: Jun 10 1991 → Jun 12 1991

Publication series

Name	Proceedings of the Annual Symposium on Computational Geometry

Other

Other	7th Annual Symposium on Computational Geometry, SCG 1991
Country/Territory	United States
City	North Conway
Period	6/10/91 → 6/12/91

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Access to Document

10.1145/109648.109656

Cite this

Computing shortest transversals of sets. / Bhattacharya, Binay; Czyzowicz, Jurek; Egyed, Peter et al.
Proceedings of the Annual Symposium on Computational Geometry. Association for Computing Machinery, 1991. p. 71-80 (Proceedings of the Annual Symposium on Computational Geometry).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bhattacharya, B, Czyzowicz, J, Egyed, P, Stojmenovic, I, Toussaint, G & Urrutia, J 1991, Computing shortest transversals of sets. in Proceedings of the Annual Symposium on Computational Geometry. Proceedings of the Annual Symposium on Computational Geometry, Association for Computing Machinery, pp. 71-80, 7th Annual Symposium on Computational Geometry, SCG 1991, North Conway, United States, 6/10/91. https://doi.org/10.1145/109648.109656

@inproceedings{c97cb3fe277749de96a0c300e6e336d6,

title = "Computing shortest transversals of sets",

abstract = "Given a family of objects in the plane, the line transversal problem is to compute a line that intersects every member of the family. In this paper we examine a variation of the line transversal problem that involves computing a shortest line segment that intersects every member of the family. In particular, we give O(nlogn) time algorithms for computing a shortest transversal of a family of n lines and of a family of n line segments. We also present an O(n log2 n) time algorithm for computing a shortest transversal of a family of polygons with a total of n vertices. In general, finding a line transversal for a family of n objects takes Ω(n log n) time. This time bound holds for a family of n line segments thus our shortest transversal algorithm for this family is optimal.",

author = "Binay Bhattacharya and Jurek Czyzowicz and Peter Egyed and Ivan Stojmenovic and Godfried Toussaint and Jorge Urrutia",

note = "Publisher Copyright: {\textcopyright} 1991 ACM.; 7th Annual Symposium on Computational Geometry, SCG 1991 ; Conference date: 10-06-1991 Through 12-06-1991",

year = "1991",

month = jun,

day = "1",

doi = "10.1145/109648.109656",

language = "English (US)",

isbn = "0897914260",

series = "Proceedings of the Annual Symposium on Computational Geometry",

publisher = "Association for Computing Machinery",

pages = "71--80",

booktitle = "Proceedings of the Annual Symposium on Computational Geometry",

}

TY - GEN

T1 - Computing shortest transversals of sets

AU - Bhattacharya, Binay

AU - Czyzowicz, Jurek

AU - Egyed, Peter

AU - Stojmenovic, Ivan

AU - Toussaint, Godfried

AU - Urrutia, Jorge

PY - 1991/6/1

Y1 - 1991/6/1

N2 - Given a family of objects in the plane, the line transversal problem is to compute a line that intersects every member of the family. In this paper we examine a variation of the line transversal problem that involves computing a shortest line segment that intersects every member of the family. In particular, we give O(nlogn) time algorithms for computing a shortest transversal of a family of n lines and of a family of n line segments. We also present an O(n log2 n) time algorithm for computing a shortest transversal of a family of polygons with a total of n vertices. In general, finding a line transversal for a family of n objects takes Ω(n log n) time. This time bound holds for a family of n line segments thus our shortest transversal algorithm for this family is optimal.

AB - Given a family of objects in the plane, the line transversal problem is to compute a line that intersects every member of the family. In this paper we examine a variation of the line transversal problem that involves computing a shortest line segment that intersects every member of the family. In particular, we give O(nlogn) time algorithms for computing a shortest transversal of a family of n lines and of a family of n line segments. We also present an O(n log2 n) time algorithm for computing a shortest transversal of a family of polygons with a total of n vertices. In general, finding a line transversal for a family of n objects takes Ω(n log n) time. This time bound holds for a family of n line segments thus our shortest transversal algorithm for this family is optimal.

UR - http://www.scopus.com/inward/record.url?scp=79951674611&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79951674611&partnerID=8YFLogxK

U2 - 10.1145/109648.109656

DO - 10.1145/109648.109656

M3 - Conference contribution

AN - SCOPUS:79951674611

SN - 0897914260

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 71

EP - 80

BT - Proceedings of the Annual Symposium on Computational Geometry

PB - Association for Computing Machinery

T2 - 7th Annual Symposium on Computational Geometry, SCG 1991

Y2 - 10 June 1991 through 12 June 1991

ER -

Computing shortest transversals of sets

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this