Computational Geometry

The Computational Geometry Group works on fonts, graph drawing and motion planning, geometric problems in manufacturing, probabalistic analysis, and vertex enumeration for convex polytopes. Click here to go to the CGM group webpages. Fonts In font design, we study the geometric, mathematical and methodological problems associated with the simulation of handwriting, random typefaces, brushed characters, running ink and linked letters. The character "6" on this page is from a typeface designed from a sample written on a magnetic pad. Our software identifies the important points of a stroke, creates smooth Bézier curves, defines glyphs based on various pen nibs, and outputs a Postscript font. Contact Luc Devroye for more info on font research.

Geometric Problems in Manufacturing There are many interesting geometric problems that arise in manufacturing. A typical example of the problems we study is the problem of finding a stable grip on an object with a robotic hand consisting of two parallel rectangular plates. The diagram on the left illustrates a particularly challenging case. Contact Godfried Toussaint for more info on this research topic.

Vertex Enumeration The theory of convex polytopes has its origins in the study of systems of linear inequalities. A (convex) polyhedron is the set of solutions to a system of linear inequalities. A bounded polyhedron is called a polytope. The vertices of a polytope are those feasible points that do not lie in the interior of a line segment between two other feasible points. Converting from the halfspaces to the vertices is called vertex enumeration. An important open problem is the existence of a vertex enumeration algorithm polynomial in the number of halfspaces plus the number of vertices. Talk to David Avis for more info on this research topic.

Graph Drawing and Motion Planning We study the layout of graphs and diagrams. For example, the picture here illustrates a 3-dimensional orthogonal grid layout of a graph. For more on the subject of graph drawing, go here. Another area of research is the design of algorithms for moving linkages and point robots. Contact Sue Whitesides for more info on this research topic.

Probabalistic Analysis We study the expected behavior of algorithms and data structures under random input or artificial randomization. Our work builds on elementary probability theory rather than combinatorial analysis. Subtopics of particular interest include random number generation and random trees. For example, we create models of random trees for simulating virtual forests. The tree on this page is a binary search tree built from a Weyl sequence (e), (2e), (3e), etcetera, where (.) denotes modulo 1. Talk to Luc Devroye for more info on this research topic.

Associated Faculty