Uses quadtrees to construct triangulations with extra Steiner vertices added to the original input. Triangulates planar point sets and polygons, with all angles bounded away from zero, using a number of triangles within a constant of optimal. Triangulates planar point sets with all angles non-obtuse, using linearly many triangles. Triangulates higher dimensional point sets with no small solid angles and a number of simplices within a constant of optimal. Augments any higher dimensional point set so the Delaunay triangulation has linear complexity.
(BibTeX -- Citations -- Preliminary copy of journal version -- MIT hypertext bibliography -- CiteSeer -- ACM DL (JCSS))
Quadtree based triangulation gives a large but constant factor approximation to the minimum weight triangulation of a point set or convex polygon, allowing extra Steiner points to be added as vertices. Includes proofs of several bounds on triangulation weight relative to the minimum spanning tree or non-Steiner triangulation, and a conjecture that for convex polygons the only points that need to be added are on the polygon boundary.
(BibTeX -- Citations -- CiteSeer)
Combines a method from "Provably good mesh generation" for finding sparse high-dimensional Delaunay triangulations, a method of Dickerson, Drysdale, and Sack ["Simple algorithms for enumerating interpoint distances", IJCGA 1992] for using Delaunay triangulations to search for nearest neighbors, and a method of Frederickson for speeding up tree-based searches. The results are fast algorithms for several proximity problems such as finding the k nearest neighbors to each point in a given point set.
(BibTeX -- Full paper -- Citations -- CiteSeer -- ACM DL)
A parallelization of the quadtree constructions in "Provably good mesh generation", in an integer model of computation, based on a technique of sorting the input points using values formed by shuffling the binary representations of the coordinates. A side-effect is an efficient construction for the "fair split tree" hierarchical clustering method used by Callahan and Kosaraju for various nearest neighbor problems.
(BibTeX -- CiteSeer -- Citations -- ACM DL)
Various authors have looked at a variant of geometric clustering in which one must select k points that can be connected by a small spanning tree. The problem is NP-complete (for variable k); good approximations are known based on dynamic programming techniques but the time dependence on n is high. This paper describes a faster approximation algorithm based on dynamic programming in quadtrees, and a general technique based on that in "Iterated nearest neighbors" for reducing the dependence on n in any approximation algorithm.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
We consider several variations of the problem of coloring the squares of a quadtree so that no two adjacent squares are colored alike. We give simple linear time algorithms for 3-coloring balanced quadtrees with edge adjacency, 4-coloring unbalanced quadtrees with edge adjacency, and 6-coloring balanced or unbalanced quadtrees with corner adjacency. The number of colors used by the first two algorithms is optimal; for the third algorithm, 5 colors may sometimes be needed.
We describe a data structure consisting of a sequence of compressed quadtrees for successively sparser samples of an input point set, with connections between the same squares in successive members of the sequence. Using this structure, we can insert or delete points and answer approximate range queries and approximate nearest neighbor queries in O(log n) time per operation.
(SoCG05 talk slides -- BibTeX)
Describes efficient distributed versions of skip quadtrees and related spatial searching structures.
Geometry -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine
Semi-automatically filtered from a common source file.