On Quadtrees, Voronoi Diagrams, and Lattices: Results in Geometric Algorithm

The unifying theme of this thesis is geometric algorithms, and somewhat more specifically algorithmic aspects of geometric structures including quadtrees, Voronoi diagrams, and lattices. It contains two parts, the first of which is on subdivision algorithms, and the second of which is on lattice algorithms..;Part I of this thesis is on subdivision algorithms. In Chapter 1, we study the amortized cost of smooth splits in quadtrees and their higher-dimensional analogs. A quadtree is smooth if any two adjacent leaf boxes differ by at most one in depth. A basic operation on a quadtree is to expand it by splitting any given leaf. We analyze quadtrees that restore smoothness after each split operation and also maintain neighbor pointers. Our main result shows that the smooth split operation in such quadtrees has an amortized cost of at most 2D ˙ ( D + 1)! auxiliary split operations, which corresponds to amortized constant time in quadtrees of any fixed dimension D..;In Chapter 2, we present a subdivision-based algorithm for computing iso-topic epsilon-approximatations of planar minimization diagrams. Given a family F = {ƒ1, . . . , ƒ n} of continuous functions with ƒi: R 2 → R, the minimization diagram of F partitions the plane into regions on which ƒi is minimal. Minimization diagrams generalize many natural Voronoi diagrams, and we show how to use our framework to compute an anisotropic Voronoi diagram on polygonal sites. We have implemented a prototype of our algorithm for anisotropic Voronoi diagrams, and provide experimental results. Our algorithm uses the smooth quadtree studied in Chapter 1 as its primary underlying data structure. We note that the focus of Chapter 2 is both more conceptual and more applied than other chapters.;Part II of this thesis is on lattice algorithms. In Chapter 3, we provide background material about linear algebra and lattices for the following chapters. In Section 3.3 we also give a high-level overview of the connections between fundamental domains, algorithms for the closest vector problem, and basis reduction which builds context for notions of basis reduction studied in the remaining two chapters.;In Chapter 4 we introduce and study the Lattice Distortion Problem (LDP). LDP asks how "similar" two lattices are, i.e., what the minimum distortion of a linear bijection between two lattices is. We first show that the distortion between any two lattices is approximated up to a nO(log n) factor by a simple function of their successive minima. Our methods are constructive, allowing us to compute low- distortion mappings with a tradeoff between approximation quality and running time. Our algorithms rely on a notion of basis reduction introduced by Seysen (Combinatorica 1993), which we show is intimately related to lattice distortion. Lastly, we show that LDP is NP-hard to approximate to within any constant factor (under randomized reductions).;Finally, in Chapter 5 we study how to compute lattices bases that (approximately) minimize two basis quality measures. Namely, we study the problem of finding bases B with low orthogonality defect delta(B) and with low Seysen condition number S(B) (the quality measure used to bound the distortion between two lattices in Chapter 4). Our main results are algorithms for computing bases B of a lattice which minimize delta(B) and (1 + epsilon)-approximately minimize S(B), while running in time only depending only on the rank of the lattice times a polynomial in the input length. Both algorithms are enumeration-based, and work by breaking a lattice into pieces according to gaps in its successive minima, a technique which may be of independent interest.