{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:24:10Z","timestamp":1760441050710,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2012,4,1]],"date-time":"2012-04-01T00:00:00Z","timestamp":1333238400000},"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":[[2012,4]]},"abstract":"<jats:p>\n            We propose designing data structures called succinct geometric indexes of negligible space (more precisely,\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) bits) that support geometric queries in optimal time, by taking advantage of the\n            <jats:italic>n<\/jats:italic>\n            points in the dataset permuted and stored elsewhere as a sequence. Our first and main result is a succinct geometric index that can answer point location queries, a fundamental problem in computational geometry, on planar triangulations in\n            <jats:italic>O<\/jats:italic>\n            (lg\n            <jats:italic>n<\/jats:italic>\n            ) time. We also design three variants of this index. The first supports point location using lg\n            <jats:italic>n<\/jats:italic>\n            + 2\u221alg\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>O<\/jats:italic>\n            (lg\n            <jats:sup>1\/4<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) point-line comparisons. The second supports point location in\n            <jats:italic>o<\/jats:italic>\n            (lg\n            <jats:italic>n<\/jats:italic>\n            ) time when the coordinates are integers bounded by\n            <jats:italic>U<\/jats:italic>\n            . The last variant can answer point location queries in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>H<\/jats:italic>\n            + 1) expected time, where\n            <jats:italic>H<\/jats:italic>\n            is the entropy of the query distribution. These results match the query efficiency of previous point location structures that occupy\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) words or\n            <jats:italic>O(n<\/jats:italic>\n            lg\n            <jats:italic>n<\/jats:italic>\n            ) bits, while saving drastic amounts of space. We generalize our succinct geometric index to planar subdivisions, and design indexes for other types of queries. Finally, we apply our techniques to design the first implicit data structures that support point location in\n            <jats:italic>O<\/jats:italic>\n            (lg\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) time.\n          <\/jats:p>","DOI":"10.1145\/2151171.2151173","type":"journal-article","created":{"date-parts":[[2012,4,24]],"date-time":"2012-04-24T18:41:10Z","timestamp":1335292870000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Succinct geometric indexes supporting point location queries"],"prefix":"10.1145","volume":"8","author":[{"given":"Prosenjit","family":"Bose","sequence":"first","affiliation":[{"name":"Carleton University, Canada"}]},{"given":"Eric Y.","family":"Chen","sequence":"additional","affiliation":[{"name":"Google Inc., California"}]},{"given":"Meng","family":"He","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}]},{"given":"Anil","family":"Maheshwari","sequence":"additional","affiliation":[{"name":"Carleton University, Canada"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[{"name":"Carleton University, Canada"}]}],"member":"320","published-online":{"date-parts":[[2012,4,25]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Eds. Contemporary Mathematics","volume":"23","author":"Agarwal P. K.","unstructured":"Agarwal , P. K. and Erickson , J . 1999. Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry, B. Chazelle, J. E. Goodman, and R. Pollack , Eds. Contemporary Mathematics , vol. 23 , American Mathematical Society Press, Providence, RI, 1--56. Agarwal, P. K. and Erickson, J. 1999. Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry, B. Chazelle, J. E. Goodman, and R. Pollack, Eds. Contemporary Mathematics, vol. 23, American Mathematical Society Press, Providence, RI, 1--56."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194272183"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446724"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 18th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science","volume":"4835","author":"Barbay J.","unstructured":"Barbay , J. , Castelli Aleardi , L. , He , M. , and Munro , J. I . 2007a. Succinct representation of labeled graphs . In Proceedings of the 18th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science , vol. 4835 , Springer-Verlag, 316--328. Barbay, J., Castelli Aleardi, L., He, M., and Munro, J. I. 2007a. Succinct representation of labeled graphs. In Proceedings of the 18th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 4835, Springer-Verlag, 316--328."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.015"},{"volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 680--689","author":"Barbay J.","key":"e_1_2_1_6_1","unstructured":"Barbay , J. , He , M. , Munro , J. I. , and Rao , S. S . 2007c. Succinct indexes for strings, binary relations and multi-labeled trees . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 680--689 . Barbay, J., He, M., Munro, J. I., and Rao, S. S. 2007c. Succinct indexes for strings, binary relations and multi-labeled trees. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 680--689."},{"key":"e_1_2_1_7_1","unstructured":"Berg M. van Kreveld M. Overmars M. and Schwarzkopf O. 1997. Computational Geometry Algorithms and Applications. Springer.   Berg M. van Kreveld M. Overmars M. and Schwarzkopf O. 1997. Computational Geometry Algorithms and Applications. Springer."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997854"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11534273_13"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137902"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.62"},{"volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. 904--911","author":"Chan T. M.","key":"e_1_2_1_12_1","unstructured":"Chan , T. M. and Chen , E. Y . 2008. In-place 2-d nearest neighbor search . In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. 904--911 . Chan, T. M. and Chen, E. Y. 2008. In-place 2-d nearest neighbor search. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. 904--911."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574703"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934990"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702411381"},{"volume-title":"Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. 383--391","author":"Clark D. R.","key":"e_1_2_1_16_1","unstructured":"Clark , D. R. and Munro , J. I . 1996. Efficient suffix trees on secondary storage . In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. 383--391 . Clark, D. R. and Munro, J. I. 1996. Efficient suffix trees on secondary storage. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. 383--391."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90004-0"},{"volume-title":"Proceedings of the 9th Canadian Conference on Computational Geometry.","author":"Denny M.","key":"e_1_2_1_18_1","unstructured":"Denny , M. and Sohler , C . 1997. Encoding a triangulation as a permutation of its point set . In Proceedings of the 9th Canadian Conference on Computational Geometry. Denny, M. and Sohler, C. 1997. Encoding a triangulation as a permutation of its point set. In Proceedings of the 9th Canadian Conference on Computational Geometry."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215023"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.69"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198521"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198516"},{"volume-title":"Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms. 757--766","author":"Goodrich M. T.","key":"e_1_2_1_24_1","unstructured":"Goodrich , M. T. , Orletsky , M. W. , 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. T., Orletsky, M. W., 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."},{"volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 841--850","author":"Grossi R.","key":"e_1_2_1_25_1","unstructured":"Grossi , R. , Gupta , A. , and Vitter , J. S . 2003. High-order entropy-compressed text indexes . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 841--850 . Grossi, R., Gupta, A., and Vitter, J. S. 2003. High-order entropy-compressed text indexes. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 841--850."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1017"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.010"},{"key":"e_1_2_1_29_1","volume-title":"Handbook of Discrete and Computational Geometry","author":"Indyk P.","unstructured":"Indyk , P. 2004. Nearest neighbors in high-dimensional spaces . In Handbook of Discrete and Computational Geometry , 2 nd Ed., J. E. Goodman and J. O'Rourke, Eds ., CRC Press , chapter 39. Indyk, P. 2004. Nearest neighbors in high-dimensional spaces. In Handbook of Discrete and Computational Geometry, 2nd Ed., J. E. Goodman and J. O'Rourke, Eds., CRC Press, chapter 39.","edition":"2"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63533"},{"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.1016\/0020-0190(79)90069-3"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90043-7"},{"volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 529--536","author":"Munro J. I.","key":"e_1_2_1_34_1","unstructured":"Munro , J. I. , Raman , V. , and Storm , A. J . 2001. Representing dynamic binary trees succinctly . In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 529--536 . Munro, J. I., Raman, V., and Storm, A. J. 2001. Representing dynamic binary trees succinctly. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 529--536."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.61"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290680"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/6138.6151"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1101"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2151171.2151173","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2151171.2151173","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:19Z","timestamp":1750241179000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2151171.2151173"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["10.1145\/2151171.2151173"],"URL":"https:\/\/doi.org\/10.1145\/2151171.2151173","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2012,4]]},"assertion":[{"value":"2009-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-04-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}