Geometric Data Structures

Tufts University, Medford MA

Investigators

Abstract

Proposal: CCF- 0830734 Title: Geometric Data Structures PI: Souvaine, Diane L. Institution: Tufts University 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 information can be retrieved quickly (query). 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 pervasive and an 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 has 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. This research project focuses on creating new and efficient data structures for geometric queries and geometric decision problems that close the gaps between known lower and upper bounds. Particular problems include planar simplex emptiness queries, relative convex hull queries in dynamic subdivisions, and dynamic vertical ray shooting queries, and the implementation of the resulting data structures in both the real RAM and word RAM models. The project also addresses key problems in computational geometry such as computing spanning trees with low crossing number, constructing minimum size cuttings in 3-space, and generating convex subdivisions from disjoint line segments in such a way as to solve plane reconfiguration problems such as the compatible geometric matching problem. Solutions to these problems will contribute to the creation of efficient data structures for geometric queries such as multi-point location, ray shooting, and range searching. These data structures are fundamental to the field of computational geometry, and have broad applications in computer graphics, robotics, CAD/CAM, motion planning, collision detection, and geographic information systems.