Sublinear Geometric Algorithms and Geometric Lower Bounds (thesis)
Abstract:
This thesis consists of two parts unified under the common theme that both of them are concerned with the complexity of geometric problems.
The first part of this thesis initiates a study of sublinear algorithms for geometric problems in two and three dimensions when no preprocessing is allowed. The problems we consider include intersection detection of convex polygons and polyhedra, point location in two-dimensional Voronoi diagrams and triangulations, ray shooting towards convex polyhedra, and nearest neighbor type problems. Our (randomized) algorithms read only a small fraction of the input. Unlike their predecessors, our algorithms never err and randomization only affects the running time but not the correctness of the output. For each problem considered (with input size n), we achieve expected running time of O(sqrt{n}), which we show to be optimal. We also approximate, for any fixed eps>0, the volume of a n-vertex convex polytope and the length of the shortest path between two points on its boundary, to within a relative factor of (1+eps) and in expected time O(sqrt{n}).
In the second part of this thesis, we prove strong lower bounds for geometric problems in standard models of computation. We prove several near-optimal lower bounds for intersection searching problems in two and three dimensions in the pointer machine model. Our lower bounds resolve a couple of long- standing open problems in computational geometry. We show
that: (1) The two- dimensional generalization of fractional cascading is impossible; (2) There exists an n-vertex convex polytope that admits of no boundary dominant Dobkin-Kirkpatrick hierarchy, for any n large enough. We also prove a near- optimal deterministic query time lower bound for Approximate Nearest Neighbor Searching -- a basic problem in computational geometry with a variety of applications -- in the cell probe model. This lower bound holds in a very special space (the Hamming Cube) and for a very loose approximation factor.
