Succinct geometric indexes supporting point location queries

ABSTRACT

We propose to design data structures called succinct geometric indexes of negligible space (more precisely, o(n) bits) that support geometric queries in optimal time, by taking advantage of the n points in the data set 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 O(lg n) time. We also design three variants of this index. The first supports point location using lg n + 2 √lg n + O(lg^1/4n) point-line comparisons. The second supports point location in o(lg n) time when the coordinates are integers bounded by U. The last variant can answer point location queries in O(H + 1) expected time, where H is the entropy of the query distribution. These results match the query efficiency of previous point location structures that occupy O(n) words or O(n lg 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 O(lg² n) time.

REFERENCES

• 1: P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. In B. Chazelle, J. E. Goodman, and R. Pollack, editors, Advances in Discrete and Computational Geometry, volume 23 of Contemporary Mathematics, pages 1--56. 1999.
• 2: L. Aleksandrov , H. Djidjev, Linear Algorithms for Partitioning Embedded Graphs of BoundedGenus, SIAM Journal on Discrete Mathematics, v.9 n.1, p.129-150, Feb. 1996 [doi>10.1137/S0895480194272183]
• 3: Sunil Arya , Theocharis Malamatos , David M. Mount , Ka Chun Wong, Optimal Expected-Case Planar Point Location, SIAM Journal on Computing, v.37 n.2, p.584-610, May 2007 [doi>10.1137/S0097539704446724]
• 4: J. Barbay, L. Castelli Aleardi, M. He, and J. I. Munro. Succinct representation of labeled graphs. In Proceedings of the 18th International Symposium on Algorithms and Computation, pages 316--328. Springer-Verlag LNCS 4835, 2007.
• 5: Jérémy Barbay , Alexander Golynski , J. Ian Munro , S. Srinivasa Rao, Adaptive searching in succinctly encoded binary relations and tree-structured documents, Theoretical Computer Science, v.387 n.3, p.284-297, November, 2007 [doi>10.1016/j.tcs.2007.07.015]
• 6: Jérémy Barbay , Meng He , J. Ian Munro , S. Srinivasa Rao, Succinct indexes for strings, binary relations and multi-labeled trees, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.680-689, January 07-09, 2007, New Orleans, Louisiana
• 7: Hervé Brönnimann , Timothy M. Chan , Eric Y. Chen, Towards in-place geometric algorithms and data structures, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997854]
• 8: L. Castelli Aleardi, O. Devillers, and G. Schaeffer. Succinct representation of triangulations with a boundary. In Proceedings of the 9th Workshop on Algorithms and Data Structures, volume 3608 of LNCS, pages 134--145. Springer, 2005.
• 9: Luca Castelli Aleardi , Olivier Devillers , Gilles Schaeffer, Optimal succinct representations of planar maps, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137902]
• 10: Timothy M. Chan, Point Location in o(log n) Time, Voronoi Diagrams in o(n log n) Time, and Other Transdichotomous Results in Computational Geometry, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.333-344, October 21-24, 2006 [doi>10.1109/FOCS.2006.62]
• 11: Timothy M. Chan , Eric Y. Chen, In-place 2-d nearest neighbor search, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.904-911, January 20-22, 2008, San Francisco, California
• 12: Yi-Ting Chiang , Ching-Chi Lin , Hsueh-I Lu, Orderly Spanning Trees with Applications, SIAM Journal on Computing, v.34 n.4, p.924-945, 2005 [doi>10.1137/S0097539702411381]
• 13: David R. Clark , J. Ian Munro, Efficient suffix trees on secondary storage, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.383-391, January 28-30, 1996, Atlanta, Georgia, United States
• 14: Richard Cole, Searching and sorting similar lists, Journal of Algorithms, v.7 n.2, p.202-220, June 1986 [doi>10.1016/0196-6774(86)90004-0]
• 15: M. Denny and C. Sohler. Encoding a triangulation as a permutation of its point set. In Proceedings of the 9th Canadian Conference on Computational Geometry, 1997.
• 16: Herbert Edelsbrunner , Lionidas J Guibas , Jorge Stolfi, Optimal point location in a monotone subdivision, SIAM Journal on Computing, v.15 n.2, p.317-340, May 1986 [doi>10.1137/0215023]
• 17: Paolo Ferragina , Fabrizio Luccio , Giovanni Manzini , S. Muthukrishnan, Structuring labeled trees for optimal succinctness, and beyond, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.184-196, October 23-25, 2005 [doi>10.1109/SFCS.2005.69]
• 18: Greg N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, v.16 n.6, p.1004-1022, December 1, 1987 [doi>10.1137/0216064]
• 19: Richard F. Geary , Rajeev Raman , Venkatesh Raman, Succinct ordinal trees with level-ancestor queries, ACM Transactions on Algorithms (TALG), v.2 n.4, p.510-534, October 2006 [doi>10.1145/1198513.1198516]
• 20: Michael T. Goodrich , Mark Orletsky , Kumar Ramaiyer, Methods for achieving fast query times in point location data structures, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.757-766, January 05-07, 1997, New Orleans, Louisiana, United States
• 21: Roberto Grossi , Ankur Gupta , Jeffrey Scott Vitter, High-order entropy-compressed text indexes, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 22: M. He. Succinct Indexes. PhD thesis, University of Waterloo, December 2007.
• 23: John Hershberger , Subhash Suri, A pedestrian approach to ray shooting: shoot a ray, take a walk, Journal of Algorithms, v.18 n.3, p.403-431, May 1995
• 24: John Iacono, Expected asymptotically optimal planar point location, Computational Geometry: Theory and Applications, v.29 n.1, p.19-22, September 2004 [doi>10.1016/j.comgeo.2004.03.010]
• 25: P. Indyk. Nearest neighbors in high-dimensional spaces. In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 39. CRC Press, 2004. 2rd edition.
• 26: G. Jacobson, Space-efficient static trees and graphs, Proceedings of the 30th Annual Symposium on Foundations of Computer Science, p.549-554, October 30-November 01, 1989 [doi>10.1109/SFCS.1989.63533]
• 27: D. G. Kirkpatrick. Optimal search in planar subdivisions. SIAM Journal on Computing, 12(1):28--35, 1983.
• 28: J Ian Munro, An implicit data structure supporting insertion, deletion, and search in O(log:OS2:OEn) time, Journal of Computer and System Sciences, v.33 n.1, p.66-74, Aug. 1986 [doi>10.1016/0022-0000(86)90043-7]
• 29: Mihai Patrascu, Planar Point Location in Sublogarithmic Time, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.325-332, October 21-24, 2006 [doi>10.1109/FOCS.2006.61]
• 30: Rajeev Raman , Venkatesh Raman , Srinivasa Rao Satti, Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets, ACM Transactions on Algorithms (TALG), v.3 n.4, p.43-es, November 2007 [doi>10.1145/1290672.1290680]
• 31: Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]
• 32: Raimund Seidel , Udo Adamy, On the exact worst case query complexity of planar point location, Journal of Algorithms, v.37 n.1, p.189-217, Oct. 2000 [doi>10.1006/jagm.2000.1101]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms