Proximate planar point location

ABSTRACT

A new data structure is presented for planar point location that executes a point location query quickly if it is spatially near the previous query. Given a triangulation T of size n and a sequence of point location queries A=q₁, q_m, the structure presented executes q_i in time O(log d(q_i-1,q_i)). The distance function, d, that is used is a two dimensional generalization of rank distance that counts the number of triangles in a region from q_i-1 to q_i. The data structure uses O(n log log n) space.

REFERENCES

• 1: Sunil Arya , Siu-Wing Cheng , David M. Mount , Ramesh Hariharan, Efficient Expected-Case Algorithms for Planar Point Location, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.353-366, July 05-07, 2000
• 2: Sunil Arya , Theocharis Malamatos , David M. Mount, Entropy-preserving cuttings and space-efficient planar point location, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.256-261, January 07-09, 2001, Washington, D.C., United States
• 3: Sunil Arya , Theocharis Malamatos , David M. Mount, A simple entropy-based algorithm for planar point location, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.262-268, January 07-09, 2001, Washington, D.C., United States
• 4: M. R. Brown and R. E. Tarjan. Design and analysis of a data structure for representing sorted lists. SIAM J. Comput., 9:594--614, 1980.
• 5: Richard Cole, On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof, SIAM Journal on Computing, v.30 n.1, p.44-85, 2000 [doi>10.1137/S009753979732699X]
• 6: Richard Cole , Bud Mishra , Jeanette Schmidt , Alan Siegel, On the Dynamic Finger Conjecture for Splay Trees. Part I: Splay Sorting log n-Block Sequences, SIAM Journal on Computing, v.30 n.1, p.1-43, 2000 [doi>10.1137/S0097539797326988]
• 7: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 8: E. Demaine, J. Iacono, and S. Langerman. Proximate point searching. In Canadian Conference on Computational Geometry, pp. 1--4, 2002.
• 9: D. P. Dobkin and R. J. Lipton. Multidimensional searching problems. SIAM J. Comput., 5:181--186, 1976.
• 10: S. Huddleston and K. Mehlhorn. A new data structure for representing sorted lists. Acta Inform., 17:157--184, 1982.
• 11: John Iacono, Improved Upper Bounds for Pairing Heaps, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.32-45, July 05-07, 2000
• 12: John Iacono, Alternatives to splay trees with O(log n) worst-case access times, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.516-522, January 07-09, 2001, Washington, D.C., United States
• 13: John Iacono, Optimal planar point location, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.340-341, January 07-09, 2001, Washington, D.C., United States
• 14: D. E. Knuth. Optimum binary search trees. Acta Inf., 1:14--25, 1971.
• 15: D. Maier and S. C. Salveter. Hysterical B-trees. Inform. Process. Lett., 12:199--202, 1981.
• 16: 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]
• 17: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms

Keywords:
planar point location