{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:17:38Z","timestamp":1750220258790,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,12,2]],"date-time":"2021-12-02T00:00:00Z","timestamp":1638403200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Research Grants Council, Hong Kong, China","award":["16201116"],"award-info":[{"award-number":["16201116"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,1,31]]},"abstract":"<jats:p>\n            We propose a dynamic data structure for the distribution-sensitive point location problem in the plane. Suppose that there is a fixed query distribution within a convex subdivision\n            <jats:italic>S<\/jats:italic>\n            , and we are given an oracle that can return in\n            <jats:italic>O<\/jats:italic>\n            (1) time the probability of a query point falling into a polygonal region of constant complexity. We can maintain\n            <jats:italic>S<\/jats:italic>\n            such that each query is answered in\n            <jats:italic>O<\/jats:italic>\n            opt\n            <jats:italic>(S)<\/jats:italic>\n            ) expected time, where opt (\n            <jats:italic>S<\/jats:italic>\n            ) is the expected time of the best linear decision tree for answering point location queries in\n            <jats:italic>S<\/jats:italic>\n            . The space and construction time are\n            <jats:italic>O(n<\/jats:italic>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ), where\n            <jats:italic>n<\/jats:italic>\n            is the number of vertices of\n            <jats:italic>S<\/jats:italic>\n            . An update of\n            <jats:italic>S<\/jats:italic>\n            as a mixed sequence of\n            <jats:italic>k<\/jats:italic>\n            edge insertions and deletions takes\n            <jats:italic>O(k<\/jats:italic>\n            log\n            <jats:sup>4<\/jats:sup>\n            n) amortized time. As a corollary, the randomized incremental construction of the Voronoi diagram of\n            <jats:italic>n<\/jats:italic>\n            sites can be performed in\n            <jats:italic>O(n<\/jats:italic>\n            log\n            <jats:sup>4<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) expected time so that, during the incremental construction, a nearest neighbor query at any time can be answered optimally with respect to the intermediate Voronoi diagram at that time.\n          <\/jats:p>","DOI":"10.1145\/3487403","type":"journal-article","created":{"date-parts":[[2021,12,2]],"date-time":"2021-12-02T15:10:11Z","timestamp":1638457811000},"page":"1-63","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Dynamic Distribution-Sensitive Point Location"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3557-9935","authenticated-orcid":false,"given":"Siu-Wing","family":"Cheng","sequence":"first","affiliation":[{"name":"HKUST, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Man-Kit","family":"Lau","sequence":"additional","affiliation":[{"name":"HKUST, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,12,2]]},"reference":[{"key":"e_1_3_5_2_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1101"},{"key":"e_1_3_5_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3046673"},{"key":"e_1_3_5_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.40"},{"key":"e_1_3_5_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446724"},{"key":"e_1_3_5_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/193253.190147"},{"key":"e_1_3_5_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214041"},{"key":"e_1_3_5_8_2","unstructured":"Prosenjit Bose Luc Devroye Karim Douieb Vida Dujmovic James King and Pat Morin. 2010. Odds-on trees. arXiv:1002.1092 Retrieved from https:\/\/arxiv.org\/abs\/1002.1092."},{"key":"e_1_3_5_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1066506"},{"key":"e_1_3_5_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01377183"},{"key":"e_1_3_5_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/0221057"},{"key":"e_1_3_5_12_2","first-page":"30:1\u201330:15","volume-title":"Proceedings of the 33rd International Symposium of Computational Geometry","author":"Cheng S.-W.","year":"2017","unstructured":"S.-W. Cheng and M.-K. Lau. 2017. Adaptive planar point location. In Proceedings of the 33rd International Symposium of Computational Geometry. 30:1\u201330:15."},{"key":"e_1_3_5_13_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195917600019"},{"key":"e_1_3_5_14_2","unstructured":"S.-W. Cheng and M.-K. Lau. 2018. Adaptive planar point location. arXiv:1810.00715 Retrieved from https:\/\/arxiv.org\/abs\/1810.00715."},{"key":"e_1_3_5_15_2","first-page":"30:1\u201330:13","volume-title":"Proceedings of the 36th International Symposium of Computational Geometry","author":"Cheng S.-W.","year":"2020","unstructured":"S.-W. Cheng and M.-K. Lau. 2020. Dynamic distribution-sensitive point location. In Proceedings of the 36th International Symposium of Computational Geometry. 30:1\u201330:13."},{"key":"e_1_3_5_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224516"},{"key":"e_1_3_5_17_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195992000184"},{"key":"e_1_3_5_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2229163.2229173"},{"key":"e_1_3_5_19_2","doi-asserted-by":"publisher","DOI":"10.5555\/646244.684395"},{"key":"e_1_3_5_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90034-2"},{"key":"e_1_3_5_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215023"},{"key":"e_1_3_5_22_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.0797"},{"key":"e_1_3_5_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793254376"},{"key":"e_1_3_5_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.010"},{"key":"e_1_3_5_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1998196.1998200"},{"key":"e_1_3_5_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"e_1_3_5_27_2","first-page":"51:1\u201351:12","volume-title":"Proceedings of the 29th International Symposium on Algorithms and Computation","author":"Oh E.","year":"2018","unstructured":"E. Oh. 2018. Point location in incremental planar subdivisions. In Proceedings of the 29th International Symposium on Algorithms and Computation. 51:1\u201351:12."},{"key":"e_1_3_5_28_2","first-page":"63:1\u201353:14","volume-title":"Proceedings of the 34th International Symposium on Computational Geometry","author":"Oh E.","year":"2018","unstructured":"E. Oh and H.-K. Ahn. 2018. Point location in dynamic planar subdivision. In Proceedings of the 34th International Symposium on Computational Geometry. 63:1\u201353:14."},{"key":"e_1_3_5_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/0218056"},{"key":"e_1_3_5_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/6138.6151"},{"key":"e_1_3_5_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/584091.584093"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3487403","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3487403","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:49Z","timestamp":1750188649000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3487403"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,2]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1,31]]}},"alternative-id":["10.1145\/3487403"],"URL":"https:\/\/doi.org\/10.1145\/3487403","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2021,12,2]]},"assertion":[{"value":"2020-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}