{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T20:18:38Z","timestamp":1648585118730},"reference-count":8,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2010,2]]},"abstract":"<jats:p> Geometric spanner is a fundamental structure in computational geometry and plays an important role in many geometric networks design applications. In this paper, we consider a generalization of the classical geometric spanner problem (called segment spanner): Given a set S of n disjoint 2-D segments, find a spanning network G<jats:sub>S<\/jats:sub> with minimum size so that for any pair of points in S, there exists a path in G<jats:sub>S<\/jats:sub> with length no more than t times their Euclidean distance. Based on a number of interesting techniques (such as weakly dominating set, strongly dominating set, interval cover, and imaginary Steiner points), we present an efficient algorithm to construct the segment spanner. Our approach first identifies a set Q of Steiner points in S and then constructs a point spanner for the set of Steiner points. Our algorithm runs in O(|Q| + n<jats:sup>2<\/jats:sup> log n) time and Q is a constant approximation (in terms of its size) of the optimal solution when S has a constant relative separation ratio. The approximation ratio depends on the stretch factor t and the relative separation ratio of S. <\/jats:p>","DOI":"10.1142\/s0218195910003190","type":"journal-article","created":{"date-parts":[[2010,3,3]],"date-time":"2010-03-03T09:31:10Z","timestamp":1267608670000},"page":"43-67","source":"Crossref","is-referenced-by-count":0,"title":["A GEOMETRIC SPANNER OF SEGMENTS"],"prefix":"10.1142","volume":"20","author":[{"given":"JINHUI","family":"XU","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, NY 14260, USA"}]},{"given":"YANG","family":"YANG","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, NY 14260, USA"}]},{"given":"YONGDING","family":"ZHU","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, NY 14260, USA"}]},{"given":"NAOKI","family":"KATOH","sequence":"additional","affiliation":[{"name":"Department of Architecture and Architectural Systems, Kyoto University, Japan"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"rf1","first-page":"179","volume":"40","author":"Aronov B.","journal-title":"Comput. Geom. Th. Appl."},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00014-0"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.09.001"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1201\/9781420010749.ch52"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382947"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187821"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884"},{"key":"rf15","first-page":"68","volume":"4705","author":"Nouri M.","journal-title":"LNCS, Computational Science and Its Applications-ICCSA"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195910003190","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T12:25:30Z","timestamp":1565094330000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195910003190"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,2]]},"references-count":8,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2010,2]]}},"alternative-id":["10.1142\/S0218195910003190"],"URL":"https:\/\/doi.org\/10.1142\/s0218195910003190","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,2]]}}}