Lower Bounds for Fundamental Geometric Problems

My thesis committee consisted of Raimund Seidel, Umesh Vazirani, and Bernd Sturmfels.

• Download the whole thing (138 pages):
• Download individual chapters:
  • Front matter: Abstract, Table of Contents, List of Figures, Acknowledgements
  • Chapter 1: Introduction
  • Part I: Adversary Lower Bounds
    • Chapter 2: Affine Degeneracies
    • Chapter 3: Convex Hull Problems
    • Chapter 4: Spherical Degeneracies
    • Chapter 5: Linear Satisfiability Problems
  • Part II: Divide-and-Conquer Lower Bounds
    • Chapter 6: Hopcroft's Problem
    • Chapter 7: Halfspace Emptiness
  • Back matter: Bibliography, Notation, Index
• Download just the quotations:

• Chapters 2-4: "Better lower bounds on detecting affine and spherical degeneracies" (but see the erratum) and "New lower bounds for convex hull problems in odd dimensions"
• Chapter 5: "Lower bounds for linear satisfiability problems"
• Chapter 6: "New lower bounds for Hopcroft's problem"
• Chapter 7: "New lower bounds for halfspace emptiness" and the journal version of "Space-time tradeoffs for emptiness queries"

Abstract:

We develop lower bounds on the number of primitive operations required to solve several fundamental problems in computational geometry. For example, given a set of points in the plane, are any three colinear? Given a set of points and lines, does any point lie on a line? These and similar questions arise as subproblems or special cases of a large number of more complicated geometric problems, including point location, range searching, motion planning, collision detection, ray shooting, and hidden surface removal.

Previously these problems were studied only in general models of computation, but known techniques for these models are too weak to prove useful results. Our approach is to consider, for each problem, a more specialized model of computation that is still rich enough to describe all known algorithms for that problem. Thus, our results formally demonstrate inherent limitations of current algorithmic techniques. Our lower bounds dramatically improve previously known results and in most cases match known upper bounds, at least up to polylogarithmic factors.

In the first part of the thesis, we develop lower bounds for several degeneracy-detection problems, using adversary arguments. For example, we show that detecting colinear triples of points requires Omega(n²) sidedness queries in the worst case. Our lower bound follows from the construction of a set of points in general position with several ``collapsible'' triangles, any one of which can be made degenerate without changing the orientation of any other triangle. Using similar techniques, we prove lower bounds for deciding, given a set of points in R^d, whether any d+1 points lie on a hyperplane, whether any d+2 points lie on a sphere, or whether the convex hull of the points is simplicial.

In the second part, we consider offline range searching problems, which are usually solved using geometric divide-and-conquer techniques. To study these problems, we introduce the class of partitioning algorithms. We prove that any partitioning algorithm requires Omega(n^4/3) time to detect point-line incidences in the worst case. Using similar techniques, we prove an Omega(n^4/3) lower bound for deciding if a set of points lies entirely above a set of hyperplanes in dimensions five and higher.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 15 Nov 1999