Nordic Journal of Computing Bibliography

Drago Krznaric and Christos Levcopoulos. Computing a Threaded Quadtree from the Delaunay Triangulation in linear time. Nordic Journal of Computing, 5(1):1-18, Spring 1998.

The 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


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database