{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:38:56Z","timestamp":1750307936874,"version":"3.41.0"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,5,1]],"date-time":"2007-05-01T00:00:00Z","timestamp":1177977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,5]]},"abstract":"<jats:p>\n            Given a planar polygonal subdivision\n            <jats:italic>S<\/jats:italic>\n            , point location involves preprocessing this subdivision into a data structure so that given any query point\n            <jats:italic>q<\/jats:italic>\n            , the cell of the subdivision containing\n            <jats:italic>q<\/jats:italic>\n            can be determined efficiently. Suppose that for each cell\n            <jats:italic>z<\/jats:italic>\n            in the subdivision, the probability\n            <jats:italic>p<\/jats:italic>\n            <jats:sub>\n              <jats:italic>z<\/jats:italic>\n            <\/jats:sub>\n            that a query point lies within this cell is also given. The goal is to design the data structure to minimize the average search time. This problem has been considered before, but existing data structures are all quite complicated. It has long been known that the entropy\n            <jats:italic>H<\/jats:italic>\n            of the probability distribution is the dominant term in the lower bound on the average-case search time. In this article, we show that a very simple modification of a well-known randomized incremental algorithm can be applied to produce a data structure of expected linear size that can answer point-location queries in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>H<\/jats:italic>\n            ) average time. We also present empirical evidence for the practical efficiency of this approach.\n          <\/jats:p>","DOI":"10.1145\/1240233.1240240","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["A simple entropy-based algorithm for planar point location"],"prefix":"10.1145","volume":"3","author":[{"given":"Sunil","family":"Arya","sequence":"first","affiliation":[{"name":"The Hong Kong University of Science and Technology, Kowloon, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Theocharis","family":"Malamatos","sequence":"additional","affiliation":[{"name":"Max Plank Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David M.","family":"Mount","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 7th Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science","volume":"1851","author":"Arya S.","unstructured":"Arya , S. , Cheng , S.-W. , Mount , D. M. , and Ramesh , H . 2000a. Efficient expected-case analysis for planar point location . In Proceedings of the 7th Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science , vol. 1851 . Springer Verlag, Berlin. 353--366. Arya, S., Cheng, S.-W., Mount, D. M., and Ramesh, H. 2000a. Efficient expected-case analysis for planar point location. In Proceedings of the 7th Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science, vol. 1851. Springer Verlag, Berlin. 353--366."},{"key":"e_1_2_1_2_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_3_1","unstructured":"Arya , S. , Malamatos , T. , and Mount , D. M . 2001. 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. 2001. Entropy-Preserving cuttings and space-efficient planar point location. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 256--261."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446724"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90004-0"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/261226"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215023"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 340--341","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. 340--341 . Iacono, J. 2001. Optimal planar point location. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 340--341."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.010"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"e_1_2_1_11_1","volume-title":"Sorting and Searching","author":"Knuth D. E.","unstructured":"Knuth , D. E. 1998. Sorting and Searching , 2 nd ed. The Art of Computer Programming, vol. 3 . Addison-Wesley , Reading, MA. Knuth, D. E. 1998. Sorting and Searching, 2nd ed. The Art of Computer Programming, vol. 3. Addison-Wesley, Reading, MA.","edition":"2"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206017"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80064-8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/6138.6151"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(91)90012-4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1101"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1240233.1240240","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1240233.1240240","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:08Z","timestamp":1750258328000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1240233.1240240"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,5]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,5]]}},"alternative-id":["10.1145\/1240233.1240240"],"URL":"https:\/\/doi.org\/10.1145\/1240233.1240240","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2007,5]]},"assertion":[{"value":"2007-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}