{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,6]],"date-time":"2024-06-06T22:39:41Z","timestamp":1717713581384},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2003,4]]},"abstract":"<jats:p> We present a new approach, called topological peeling, for traversing a portion A<jats:sub>R<\/jats:sub> of the arrangement formed by n lines within a convex region R on the plane. Topological peeling visits the cells of A<jats:sub>R<\/jats:sub> in a fashion of propagating a \"wave\" of a special shape (called a double-wriggle curve) starting at a single source point. This special traversal fashion enables us to solve several problems (e.g., computing shortest paths) on planar arrangements to which previously best known arrangement traversal techniques such as topological sweep and topological walk may not be directly applicable. Our topological peeling algorithm takes O(K + n log (n + r)) time and O(n + r) space, where K is the number of cells in A<jats:sub>R<\/jats:sub> and r is the number of boundary vertices of R. Comparing with topological walk, topological peeling uses a simpler and more efficient way to sweep different types of lines, and relies heavily on exploring small local structures, rather than a much larger global structure. Experiments show that, on average, topological peeling outperforms topological walk by 10\u201325% in execution time. <\/jats:p>","DOI":"10.1142\/s0218195903001104","type":"journal-article","created":{"date-parts":[[2003,4,24]],"date-time":"2003-04-24T12:35:43Z","timestamp":1051187743000},"page":"135-172","source":"Crossref","is-referenced-by-count":6,"title":["TOPOLOGICAL PEELING AND APPLICATIONS"],"prefix":"10.1142","volume":"13","author":[{"given":"DANNY Z.","family":"CHEN","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556, USA"}]},{"given":"SHUANG","family":"LUAN","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556, USA"}]},{"given":"JINHUI","family":"XU","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, State University of New York at Buffalo, 201 Bell Hall, Buffalo, NY 14260, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574380"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009204"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195994000094"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934990"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90038-X"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1145\/77635.77639"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1137\/0215024"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1137\/0215019"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1990.10475313"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80033-X"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1145\/358656.358681"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195903001104","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:20:07Z","timestamp":1565191207000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195903001104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,4]]},"references-count":13,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2003,4]]}},"alternative-id":["10.1142\/S0218195903001104"],"URL":"https:\/\/doi.org\/10.1142\/s0218195903001104","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,4]]}}}