{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,10]],"date-time":"2024-02-10T09:39:13Z","timestamp":1707557953892},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1992,12]]},"abstract":"<jats:p> 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(n log n) time algorithms for computing a shortest transversal of a family of n lines, a family of n line segments, and a family of convex polygons with a total of n vertices. In general, finding a line transversal for a family of n objects takes \u03a9(n log n) time. This time bound holds for a family of n line segments as well as for a family of convex polygons with a total of n vertices. Hence, our shortest transversal algorithms for these families are optimal. <\/jats:p>","DOI":"10.1142\/s0218195992000238","type":"journal-article","created":{"date-parts":[[2004,11,24]],"date-time":"2004-11-24T19:50:24Z","timestamp":1101325824000},"page":"417-435","source":"Crossref","is-referenced-by-count":4,"title":["COMPUTING SHORTEST TRANSVERSALS OF SETS"],"prefix":"10.1142","volume":"02","author":[{"given":"BINAY","family":"BHATTACHARYA","sequence":"first","affiliation":[{"name":"School of Computing Science, Simon Fraser University, Burnaby, British Columbia, Canada V5A 1S6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JUREK","family":"CZYZOWICZ","sequence":"additional","affiliation":[{"name":"D\u00e9partement d\u2019Informatique, Universit\u00e9 du Qu\u00e9bec \u00e0 Hull, Hull, Qu\u00e9bec, Canada J8X 3X7, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PETER","family":"EGYED","sequence":"additional","affiliation":[{"name":"School of Computer Science, McGill University, Montreal, Quebec, Canada H3A 2A7, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"GODFRIED","family":"TOUSSAINT","sequence":"additional","affiliation":[{"name":"School of Computer Science, McGill University, Montreal, Quebec, Canada H3A 2A7, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"IVAN","family":"STOJMENOVIC","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Ottawa, Ottawa, Ontario, Canada K1N 6N5, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JORGE","family":"URRUTIA","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Ottawa, Ottawa, Ontario, Canada K1N 6N5, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195992000238","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T10:57:06Z","timestamp":1565175426000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195992000238"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,12]]},"references-count":0,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1992,12]]}},"alternative-id":["10.1142\/S0218195992000238"],"URL":"https:\/\/doi.org\/10.1142\/s0218195992000238","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,12]]}}}