Theses & Reports

---

Instructions for submitting a technical report or thesis.

You can find technical reports published prior to 1990 archived here.

• Ph.D. Thesis 1979 On Quadtrees, Voronoi Diagrams, and Lattices: Results in Geometric Algorithms Bennett, Huxley Abstract | PDF

  Title: On Quadtrees, Voronoi Diagrams, and Lattices: Results in Geometric Algorithms

  Candidate: Bennett, Huxley

  Advisor(s): Chee Yap

  Abstract:

  We present several results on geometric algorithms, and somewhat more specifically on algorithmic aspects of geometric structures including quadtrees, Voronoi diagrams, and lattices. Our work contains two parts, the first of which is on subdivision algorithms, and the second of which is on lattice algorithms.

  Subdivision algorithms amount to recursively splitting an ambient space into smaller pieces until certain conditions hold. Often the underlying space is a square in the plane (or a box in higher dimensions), whose subdivision is represented by a quadtree (or its higher-dimensional analogs). A quadtree is smooth if any two adjacent leaf boxes differ by at most one in depth. We first study the cost of the smooth split operation in quadtrees, showing that it has constant amortized cost in quadtrees of any fixed dimension.

  We then present a subdivision-based algorithm for computing isotopic epsilon-approximations of planar minimization diagrams. Given a family of continuous functions, its minimization diagram partitions the plane into regions on which each function 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 we provide experimental results.

  We then turn to studying lattice algorithms. A lattice is a regular ordering of points in Euclidean space, which is represented as the set of all integer combinations of some linearly independent vectors (which we call a basis of the lattice). In our first work on lattices, 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 show how to compute low-distortion mappings with a tradeoff between approximation quality and running time based on a notion of basis reduction introduced by Seysen (Combinatorica 1993). We also show that LDP is NP-hard to approximate to within any constant factor (under randomized reductions).

  Finally, we study the problem of finding lattice bases which are optimal with respect to two basis quality measures. Namely, we study the problem of finding bases with minimal orthogonality defect, and with nearly minimal Seysen condition number. We give algorithms which solve both problems while running in time depending only on the rank of the lattice times a polynomial in the input length.

• Ph.D. Thesis 1979 Automatic Storage Optimization Fabri, Janet Abstract | PDF
• Ph.D. Thesis 1979 The Optimization of Horizontal Microcode within and Beyond Basic Blocks: an Application of Processor Scheduling with Resources Fisher, Joseph Allen Abstract | PDF
• Ph.D. Thesis 1979 On the Complexity of the Satisfiability Problem Goldberg, Allen T. Abstract | PDF
• Ph.D. Thesis 1979 Computing Chromatic Polynomials for Special Families of Graphs Loerinc, Beatrice Margaret Abstract | PDF
• Ph.D. Thesis 1979 Expression Continuity and the Formal Differentiation of Algorithms Paige, Robert Allan Abstract | PDF
• Ph.D. Thesis 1979 Comparison of Direct Code Generation and Intermediate Language Generationfor Bootstrapping the Machine-Independent Compiler, Little Schneck, Paul Bennett Abstract | PDF
• Ph.D. Thesis 1979 Groups with Solvable Word Problems Semeniuk, Christine Abstract | PDF
• Ph.D. Thesis 1979 Automatic Discovery of Heuristics for Nondeterministic Programs from Sample Execution Traces Stolfo, Salvatore Joseph Abstract | PDF