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

N1 - Publisher Copyright:
© 1991 ACM.

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 -