Computational Geometry
Department of Computer Science
Research Topics
Geometric Graph Theory
A geometric representation of a graph is mapping that assigns vertices and edges of the graph to geometric objects. We are usually interested in drawings of graphs in a plane. A topological graph represents vertices by points and edges by curves (Jordan arcs). A geometric graph is a topological graph whose edges are represented by straight line segments. Graph drawings have several applications in information visualization, cartogrphy, social network analysis, etc.
Our research focus on topics including:
• Optmization problems concerning geometric graphs such as augmenting the connectivity and multi-colored spanning graphs.
• Detecting crossings in drawings with overlapping vertices and edges.
• Simultanious drawings of graphs on the same point set.
Reconfiguration through descrete moves
Modeling continuous motion with decrete elementary operations leads to more efficient computational tools. Applications include motion planning algorithms and corresponding dynamic data structures for bar-and-joint frameworks, hinged polygons, and disk arrangements, motivated by applications in protein folding. Current challenges include designing efficient data structures to support shortest path computation in the configuration space, approximating the diameter and radius of configuration spaces, and deciding whether reconfiguration is possible.
Geometric Data Structures
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. Our research has been focused on creating new and efficient geometric data structures that close the gaps between known lower and upper bounds. Particular topics include:
• Relative Convex Hulls
• Simplex Range Searching
• Ray Shooting and Insertion
• Convex Partitioning
Self Assembly
Self-assembly is the programmic design of simple particle systems that coalesce into complex superstructures. The design of these systems combines geometry and computation in novel ways to carry out computation by the physical interactions between particles. See David Doty's recent survey article for an overview of recent work in these systems, or a description of some of our work.
Data Depth & Computational Statistics

Data Depth extends the concept of univariate rank into higher dimensions. Essentially, given a cloud of points in n dimensions, how deep is a point, relative to the entire cloud? Additionally, we can use depth to determine the median of a multivariate data set.

 Go to our Data Depth page with more general information and links to our Data Depth research and projects. Data Depth Overview Or jump right to a Data Depth sub-page...
Other Topics
Algorithms for solving Rubik's cubes.
Topological Sweep
Crossing number for points and segments
Finding Knots and Links in Vector Fields