AbstractThe quadtree in this paper is a variant in which two nodes are threaded (linked) if they represent equal-sized squares that are sufficiently close to each other. Given the Delaunay triangulation, it is shown that the threaded quadtree can be computed in linear time and space. It is also described how the threaded quadtree can be used to answer certain types of non-trivial range queries in constant time per query, which has applications, for example, in computing the greedy triangulation, the complete linkage clustering, and a constant-factor approximation of minimum weight triangulation. These queries ask for links to and information concerning the contents of growing ranges, including values of functions based on these contents.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; E.1 [Data Structures]; I.4.1 [Image Processing]: Digitization
Additional Key Words and Phrases: analysis of algorithms, computational geometry, quadtree, Delaunay triangulation
Selected references
- David Cheriton and Robert Endre Tarjan. Finding minimum spanning trees. SIAM Journal on Computing, 5(4):724-742, December 1976.
- Dov Harel and Robert Endre Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing, 13(2):338-355, May 1984.
- Christos Levcopoulos and Drago Krznaric. Quasi-greedy triangulations approximating the minimum weight triangulation. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 392-401, Atlanta, Georgia, 28-30 January 1996.
- Christos Levcopoulos and Drago Krznaric. A fast heuristic for approximating the minimum weight triangulation (extended abstract). In Rolf G. Karlsson and Andrzej Lingas, editors, SWAT '96, 5th Scandinavian Workshop on Algorithm Theory, volume 1097 of Lecture Notes in Computer Science, pages 296-308, Reykjavík, Iceland, 3-5 July 1996. Springer.
- Robert Endre Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2):215-225, April 1975.
- Cao An Wang and Francis Y. Chin. Finding the constrained Delaunay triangulation and constrainted Voronoi diagram of a simple polygon in linear-time (extended abstract). In Paul G. Spirakis, editor, Algorithms -- ESA '95, Third Annual European Symposium, volume 979 of Lecture Notes in Computer Science, pages 280-294, Corfu, Greece, 25-27 September 1995. Springer.