PhD Defense: Geometric Data Structures

Abstract

A data structure is a repository of information; the goal is to organize the data so that it needs less storage (space) and so that a request for information (query) can be processed quickly. A geometric data structure handles data which has locations attached to it (e.g. addresses of fire stations in the state of Massachusetts). Geometric data structures have become a pervasive and integral part of life, and can be queried to produce driving directions or the name of the nearest Italian restaurant. Since the space and query time of a data structure depend upon the type of queries it needs to support, it is important to study which tools and techniques are suitable for which data structures. The ongoing quest for better data structures sometimes results in improved methods and sometimes results in entirely new techniques. The goal is to determine optimal data structures with the best possible performance.

In this thesis, we prove new lower bounds for simplex emptiness queries in the partition graph model. Given a set of points in the euclidean space, a data structure for simplex emptiness can report whether a query simplex contains any point. Our lower bounds are based on the lower bounds provided by Erickson for online hyperplane emptiness problem in the partition graph model, and are within a polylogarithmic factor of the optimal in the plane.

Although the lower bounds paint a very pessimistic picture for the possibility of efficient data structures, these data structures do notexist in vacuum but are used by applications (algorithms) which may have some special structure. For example Paterson and Yao's classical randomized auto-partition algorithm could be implemented using a dynamic ray shooting data structure, but the algorithm does not ``really need'' a general ray shooting data structure. We were able to improve the runtime of the algorithm by developing a new data structure for ray shooting-and-insertion in the free space around disjoint polygonal obstacles.

Finally we give an algorithm to produce convex partitions with 2-edge connected dual graphs--a useful tool in creating efficient data structures. For example, binary space partitions (a type of convex partition) are used to implement efficiently the "painter's algorithm" for rendering scenes in computer graphics.