Efficient algorithms for proximity problems
Young Cheul Wee · 1989
Computational geometry is currently a very active area of research in computer science because of its applications to VLSI design, database retrieval, robotics, pattern recognition, etc. We study a number of proximity problems which are fundamental in computational geometry. Optimal or improved sequential and parallel algorithms for these problems are presented. Along the way, some relations among the proximity problems are also established. Chapter 2 presents an $O(N$ log$\sp2$ N) time divide-and-conquer algorithm for solving the all pairs geographic nearest neighbors problem (GNN) for a set of N sites in the plane under any $L\sb{p}$ metric. Chapter 3 presents an $O(N$ log $N)$ divide-and-conquer algorithm for computing the angle restricted Voronoi diagram for a set of N sites in the plane. We establish relations among some proximity problems that hold for generalized distance functions. Chapter 4 introduces a new data structure for the dynamic version of GNN. Using this data structure, we improve the running times of the heuristics discussed in (Bern 88) from $O(N\sp2$ log $N)$ to $O(N$ log$\sp2$ N). We extend the ideas developed in this context to design an optimal $O(N$ log $N)$ algorithm for the construction of a rectilinear minimum spanning tree for a set of N non-crossing line segments in the plane. Chapter 5 defines a new formalism called the quasi-valid range aggregation. This formalism leads to a new and simple method for reducing non-range query-like problems to range queries and often to orthogonal range queries, with immediate applications to the attracted neighbor and the planar all-pairs nearest neighbors problem. A point of interest is that our new formalism permits operators + that are neither associative nor abelian (unlike traditional range query theory). Chapter 6 introduces a new approach for the construction of the Voronoi diagram. Using this approach, we design an $O($log $N)$ time $O(N)$ processor algorithm for constructing the Voronoi diagram with $L\sb1$ and $L\sb\infty$ metrics on a CREW PRAM machine. Even though the GNN and the Delaunay triangulation (DT) do not have an inclusion relation, we show, using some range type queries, how to efficiently construct DT from the GNN relations over a constant number of angular ranges. (Abstract shortened with permission of author.)