{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:23:23Z","timestamp":1750307003146,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,7,1]],"date-time":"2012-07-01T00:00:00Z","timestamp":1341100800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["OISE-0334653 and CCF-0430849"],"award-info":[{"award-number":["OISE-0334653 and CCF-0430849"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000089","name":"Office of International Science and Engineering","doi-asserted-by":"publisher","award":["OISE-0334653 and CCF-0430849"],"award-info":[{"award-number":["OISE-0334653 and CCF-0430849"]}],"id":[{"id":"10.13039\/100000089","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>\n            A data structure is presented for point location in connected planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that is within a constant factor of optimal. More specifically, an algorithm is presented that preprocesses a connected planar subdivision\n            <jats:italic>G<\/jats:italic>\n            of size\n            <jats:italic>n<\/jats:italic>\n            and a query distribution\n            <jats:italic>D<\/jats:italic>\n            to produce a point location data structure for\n            <jats:italic>G<\/jats:italic>\n            . The expected number of point-line comparisons performed by this data structure, when the queries are distributed according to\n            <jats:italic>D<\/jats:italic>\n            , is H\u02dc +\n            <jats:italic>O<\/jats:italic>\n            (H\u02dc\n            <jats:sup>1\/2<\/jats:sup>\n            +1) where H\u02dc=H\u02dc(\n            <jats:italic>G,D<\/jats:italic>\n            ) is a lower bound on the expected number of point-line comparisons performed by any linear decision tree for point location in\n            <jats:italic>G<\/jats:italic>\n            under the query distribution\n            <jats:italic>D<\/jats:italic>\n            . The preprocessing algorithm runs in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) time and produces a data structure of size\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ). These results are obtained by creating a Steiner triangulation of\n            <jats:italic>G<\/jats:italic>\n            that has near-minimum entropy.\n          <\/jats:p>","DOI":"10.1145\/2229163.2229173","type":"journal-article","created":{"date-parts":[[2012,7,26]],"date-time":"2012-07-26T14:41:09Z","timestamp":1343313669000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Entropy, triangulation, and point location in planar subdivisions"],"prefix":"10.1145","volume":"8","author":[{"given":"S\u00e9bastien","family":"Collette","sequence":"first","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vida","family":"Dujmovi\u0107","sequence":"additional","affiliation":[{"name":"Carleton University, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Iacono","sequence":"additional","affiliation":[{"name":"Polytechnic Institute of NYU, Brooklyn, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Langerman","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles, Natural ICT Australia, University of Sydney, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,7,24]]},"reference":[{"volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. 609--618","author":"Adamy U.","key":"e_1_2_1_1_1","unstructured":"Adamy , U. and Seidel , R . 1998. On the exact worst case query complexity of planar point location . In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. 609--618 . Adamy, U. and Seidel, R. 1998. On the exact worst case query complexity of planar point location. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. 609--618."},{"volume-title":"Proceedings of the 7th Scandinavian Workshop on Algorithm Theory. 353--366","author":"Arya S.","key":"e_1_2_1_2_1","unstructured":"Arya , S. , Cheng , S. W. , Mount , D. M. , and Ramesh , H . 2000a. Efficient expected-case algorithms for planar point location . In Proceedings of the 7th Scandinavian Workshop on Algorithm Theory. 353--366 . Arya, S., Cheng, S. W., Mount, D. M., and Ramesh, H. 2000a. Efficient expected-case algorithms for planar point location. In Proceedings of the 7th Scandinavian Workshop on Algorithm Theory. 353--366."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796603"},{"volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 256--261","author":"Arya S.","key":"e_1_2_1_4_1","unstructured":"Arya , S. , Malamatos , T. , and Mount , D. M . 2001a. Entropy-Preserving cuttings and space-efficient planar point location . In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 256--261 . Arya, S., Malamatos, T., and Mount, D. M. 2001a. Entropy-Preserving cuttings and space-efficient planar point location. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 256--261."},{"volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 262--268","author":"Arya S.","key":"e_1_2_1_5_1","unstructured":"Arya , S. , Malamatos , T. , and Mount , D. M . 2001b. A simple entropy-based algorithm for planar point location . In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 262--268 . Arya, S., Malamatos, T., and Mount, D. M. 2001b. A simple entropy-based algorithm for planar point location. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 262--268."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446724"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1287-2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.62"},{"volume-title":"Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA'08)","author":"Collette S.","key":"e_1_2_1_9_1","unstructured":"Collette , S. , Dujmovi\u0107 , V. , Iacono , J. , Langerman , S. , and Morin , P . 2008. Distribution-Sensitive point location in convex subdivisions . In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA'08) . 912--921. Collette, S., Dujmovi\u0107, V., Iacono, J., Langerman, S., and Morin, P. 2008. Distribution-Sensitive point location in convex subdivisions. In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA'08). 912--921."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205015"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215023"},{"volume-title":"Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms. 757--766","author":"Goodrich M.","key":"e_1_2_1_13_1","unstructured":"Goodrich , M. , Orletsky , M. , and Ramaiyer , K . 1997. Methods for achieving fast query times in point location data structures . In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms. 757--766 . Goodrich, M., Orletsky, M., and Ramaiyer, K. 1997. Methods for achieving fast query times in point location data structures. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms. 757--766."},{"key":"e_1_2_1_14_1","unstructured":"Gray R. M. 2008. Entropy and Information Theory. http:\/\/www-ee.stanford.edu\/~gray\/it.html.  Gray R. M. 2008. Entropy and Information Theory. http:\/\/www-ee.stanford.edu\/~gray\/it.html."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 240--241","author":"Iacono J.","year":"2001","unstructured":"Iacono , J. 2001 . Optimal planar point location . In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 240--241 . Iacono, J. 2001. Optimal planar point location. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 240--241."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.010"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206043"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264563"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80064-8"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210035"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054190000072"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.61"},{"key":"e_1_2_1_24_1","volume-title":"Contemporary Mathematics Series","volume":"453","author":"Rote G.","unstructured":"Rote , G. , Santos , F. , and Steinu , I . 2006. Pseudo-Triangulations\u2014A survey. In Surveys on Discrete and Computational Geometry\u2014Twenty Years Later, J. E. Goodman, J. Pach, and R. Pollack, Eds ., Contemporary Mathematics Series , vol. 453 , American Mathematical Society, 343--410. Rote, G., Santos, F., and Steinu, I. 2006. Pseudo-Triangulations\u2014A survey. In Surveys on Discrete and Computational Geometry\u2014Twenty Years Later, J. E. Goodman, J. Pach, and R. Pollack, Eds., Contemporary Mathematics Series, vol. 453, American Mathematical Society, 343--410."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/6138.6151"},{"key":"e_1_2_1_26_1","article-title":"A mathematical theory of communication. Bell","author":"Shannon C. E.","year":"1948","unstructured":"Shannon , C. E. 1948 . A mathematical theory of communication. Bell Syst. Tech. J., 379--423 and 623--656. Shannon, C. E. 1948. A mathematical theory of communication. Bell Syst. Tech. J., 379--423 and 623--656.","journal-title":"Syst. Tech. J., 379--423 and 623--656."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2229163.2229173","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2229163.2229173","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:48:52Z","timestamp":1750236532000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2229163.2229173"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.1145\/2229163.2229173"],"URL":"https:\/\/doi.org\/10.1145\/2229163.2229173","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2012,7]]},"assertion":[{"value":"2009-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-07-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}