{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T22:53:57Z","timestamp":1672613637632},"reference-count":18,"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> Consider a geometric network G in the plane. The dilation between any two vertices x and y in G is the ratio of the shortest path distance between x and y in G to the Euclidean distance between them. The maximum dilation over all pairs of vertices in G is called the dilation of G. In this paper, a randomized algorithm is presented which, when given a polygonal cycle C on n vertices in the plane, computes in O(n log <jats:sup>3<\/jats:sup> n) expected time, the edge of C whose removal results in a polygonal path of smallest possible dilation. It is also shown that the edge whose removal gives a polygonal path of largest possible dilation can be computed in O(n log n) time. If C is a convex polygon, the running time for the latter problem becomes O(n). Finally, it is shown that a (1 - \u03f5)-approximation to the dilation of every path C \\{e}, for all edges e of C, can be computed in O(n log n) total time. <\/jats:p>","DOI":"10.1142\/s0218195910003207","type":"journal-article","created":{"date-parts":[[2010,3,3]],"date-time":"2010-03-03T09:31:10Z","timestamp":1267608670000},"page":"69-87","source":"Crossref","is-referenced-by-count":1,"title":["DILATION-OPTIMAL EDGE DELETION IN POLYGONAL CYCLES"],"prefix":"10.1142","volume":"20","author":[{"given":"HEE-KAP","family":"AHN","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Pohang University of Science and Technology, Pohang, 790-784, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MOHAMMAD","family":"FARSHI","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University, Ottawa, Ontario, K1S 5B6, Canada"},{"name":"Department of Computer Science, Yazd University, P.O. Box. 89195-741, Yazd, Iran"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CHRISTIAN","family":"KNAUER","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Freie Universit\u00e4t Berlin, Takustra\u00dfe 9, D\u201314195 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MICHIEL","family":"SMID","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carleton University, Ottawa, Ontario, K1S 5B6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YAJUN","family":"WANG","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-007-9019-9"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187749"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200853"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.12.001"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195992000147"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1137\/0215023"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.05.007"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1137\/050635675"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840357"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70904-6_20"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90066-2"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000167"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361671"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546884"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0013-1"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044482537-7\/50021-8"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195910003207","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T12:25:31Z","timestamp":1565094331000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195910003207"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,2]]},"references-count":18,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2010,2]]}},"alternative-id":["10.1142\/S0218195910003207"],"URL":"https:\/\/doi.org\/10.1142\/s0218195910003207","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,2]]}}}