Home People Papers & Presentations Courses Software Geometry Links

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.

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. 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 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 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... Depth Explorer Proximity Depth Half-Space Depth Simplicial Depth

Algorithms for solving Rubik's cubes.

• Topological Sweep in Degenerated Cases
• Topologically Sweeping the complete graph
• LMS Regression using Guided Topological Sweep