{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:06:39Z","timestamp":1787501199188,"version":"build-2736575974"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,4,13]],"date-time":"2015-04-13T00:00:00Z","timestamp":1428883200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1217906, CCF-1317143"],"award-info":[{"award-number":["CCF-1217906, CCF-1317143"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2015,6,23]]},"abstract":"<jats:p>\n                    A fundamental problem in computational geometry is to compute an obstacle-avoiding Euclidean shortest path between two points in the plane. The case of this problem on polygonal obstacles is well studied. In this article, we consider the problem version on curved obstacles, which are commonly modeled as\n                    <jats:italic>splinegons<\/jats:italic>\n                    . A splinegon can be viewed as replacing each edge of a polygon by a convex curved edge (polygons are special splinegons), and the combinatorial complexity of each curved edge is assumed to be\n                    <jats:italic>O<\/jats:italic>\n                    (1). Given in the plane two points\n                    <jats:italic>s<\/jats:italic>\n                    and\n                    <jats:italic>t<\/jats:italic>\n                    and a set\n                    <jats:italic>s<\/jats:italic>\n                    of\n                    <jats:italic>h<\/jats:italic>\n                    pairwise disjoint splinegons with a total of\n                    <jats:italic>n<\/jats:italic>\n                    vertices, after a\n                    <jats:italic>bounded degree decomposition<\/jats:italic>\n                    of\n                    <jats:italic>S<\/jats:italic>\n                    is obtained, we compute a shortest\n                    <jats:italic>s<\/jats:italic>\n                    -to-\n                    <jats:italic>t<\/jats:italic>\n                    path avoiding the splinegons in\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    +\n                    <jats:italic>h<\/jats:italic>\n                    \u2009log\u2009\n                    <jats:italic>h<\/jats:italic>\n                    +\n                    <jats:italic>k<\/jats:italic>\n                    ) time, where\n                    <jats:italic>k<\/jats:italic>\n                    is a parameter sensitive to the geometric structures of the input and is upper bounded by\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>h<\/jats:italic>\n                    <jats:sup>2<\/jats:sup>\n                    ). The bounded degree decomposition of\n                    <jats:italic>S<\/jats:italic>\n                    , which is similar to the triangulation of the polygonal domains, can be computed in\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    \u2009log\u2009\n                    <jats:italic>n<\/jats:italic>\n                    ) time or\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    +\n                    <jats:italic>h<\/jats:italic>\n                    \u2009log\u2009\n                    <jats:sup>1 + \u03f5<\/jats:sup>\n                    <jats:italic>h<\/jats:italic>\n                    ) time for any \u03f5 &gt; 0. In particular, when all splinegons are convex, the decomposition can be computed in\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    +\n                    <jats:italic>h<\/jats:italic>\n                    \u2009log\u2009\n                    <jats:italic>h<\/jats:italic>\n                    ) time and\n                    <jats:italic>k<\/jats:italic>\n                    is linear to the number of common tangents in the free space (called \u201cfree common tangents\u201d) among the splinegons. Our techniques also improve several previous results:\n                  <\/jats:p>\n                  <jats:p>\n                    (1) For the polygon case (i.e., when all splinegons are polygons), the shortest path problem was previously solved in\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    \u2009log\u2009\n                    <jats:italic>n<\/jats:italic>\n                    ) time, or in\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    +\n                    <jats:italic>h<\/jats:italic>\n                    <jats:sup>2<\/jats:sup>\n                    log\u2009\n                    <jats:italic>n<\/jats:italic>\n                    ) time. Thus, our algorithm improves the\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    +\n                    <jats:italic>h<\/jats:italic>\n                    <jats:sup>2<\/jats:sup>\n                    log\u2009\n                    <jats:italic>n<\/jats:italic>\n                    ) time result, and is faster than the\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    \u2009log\u2009\n                    <jats:italic>n<\/jats:italic>\n                    ) time solution for sufficiently small\n                    <jats:italic>h<\/jats:italic>\n                    , for example,\n                    <jats:italic>h<\/jats:italic>\n                    =\n                    <jats:italic>o<\/jats:italic>\n                    (\u221a\n                    <jats:italic>n<\/jats:italic>\n                    ,log\n                    <jats:italic>n<\/jats:italic>\n                    .\n                  <\/jats:p>\n                  <jats:p>\n                    (2) Our techniques produce an optimal output-sensitive algorithm for a basic visibility problem of computing all free common tangents among\n                    <jats:italic>h<\/jats:italic>\n                    pairwise disjoint convex splinegons with a total of\n                    <jats:italic>n<\/jats:italic>\n                    vertices. Our algorithm runs in\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    +\n                    <jats:italic>h<\/jats:italic>\n                    \u2009log\u2009\n                    <jats:italic>h<\/jats:italic>\n                    +\n                    <jats:italic>k<\/jats:italic>\n                    ) time and\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    ) working space, where\n                    <jats:italic>k<\/jats:italic>\n                    is the number of all free common tangents. Note that\n                    <jats:italic>k<\/jats:italic>\n                    =\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>h<\/jats:italic>\n                    <jats:sup>2<\/jats:sup>\n                    ). Even for the special case where all splinegons are convex\n                    <jats:italic>polygons<\/jats:italic>\n                    , the previously best algorithm for this visibility problem takes\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    +\n                    <jats:italic>h<\/jats:italic>\n                    <jats:sup>2<\/jats:sup>\n                    log\u2009\n                    <jats:italic>n<\/jats:italic>\n                    ) time.\n                  <\/jats:p>\n                  <jats:p>\n                    (3) We improve the previous work for computing the shortest path between two points among convex pseudodisks of\n                    <jats:italic>O<\/jats:italic>\n                    (1) complexity each.\n                  <\/jats:p>\n                  <jats:p>\n                    In addition, a by-product of our techniques is an optimal\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    +\n                    <jats:italic>h<\/jats:italic>\n                    \u2009log\u2009\n                    <jats:italic>h<\/jats:italic>\n                    ) time and\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    ) space algorithm for computing the Voronoi diagram of a set of\n                    <jats:italic>h<\/jats:italic>\n                    pairwise disjoint convex splinegons with a total of\n                    <jats:italic>n<\/jats:italic>\n                    vertices.\n                  <\/jats:p>","DOI":"10.1145\/2660771","type":"journal-article","created":{"date-parts":[[2015,4,14]],"date-time":"2015-04-14T08:32:19Z","timestamp":1429000339000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Computing Shortest Paths among Curved Obstacles in the Plane"],"prefix":"10.1145","volume":"11","author":[{"given":"Danny Z.","family":"Chen","sequence":"first","affiliation":[{"name":"University of Notre Dame, Notre Dame, IN"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haitao","family":"Wang","sequence":"additional","affiliation":[{"name":"Utah State University, Logan, UT"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,4,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840436"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195994000252"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064092.1064112"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574703"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/110840030"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582125"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201911)","author":"Chen D. Z."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 19th European Symposium on Algorithms (ESA\u201911)","author":"Chen D. Z."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_19"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462356.2462377"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of 30th Symposium on Theoretical Aspects of Computer Science (STACS\u201913)","author":"Chen D. Z."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40104-6_22"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/323233.323261"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840397"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762127"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90038-X"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215023"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840357"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220055"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840360"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90003-X"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289604"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2462356.2462374"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80033-X"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.02.005"},{"key":"e_1_2_1_26_1","unstructured":"R. Inkulu S. Kapoor and S. N. Maheshwari. 2010. A near optimal algorithm for finding Euclidean shortest path in polygonal domain. In arXiv:1011.6481v1.  R. Inkulu S. Kapoor and S. N. Maheshwari. 2010. A near optimal algorithm for finding Euclidean shortest path in polygonal domain. In arXiv:1011.6481v1."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/73393.73411"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009323"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2805882.2806037"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the International Conference on Computational Science and Its Applications. 62--70","author":"Kim D.-S."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2383356.2383359"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02716580"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221038"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195996000216"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/73393.73410"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/220279.220306"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02712876"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90045-1"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.185795"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90044-4"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2660771","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2660771","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:56:13Z","timestamp":1750215373000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2660771"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,13]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,6,23]]}},"alternative-id":["10.1145\/2660771"],"URL":"https:\/\/doi.org\/10.1145\/2660771","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,13]]},"assertion":[{"value":"2013-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}