CRA-W/CDC Workshop on
Computational Geometry: Abstracts

Joseph O'Rourke (Smith College) [view bio]

Curve Shortening, Geodesics, and the Poincaré Conjecture

A time series can be smoothed by averaging nearby samples to aggregate data and remove noise. This is a simple and obvious transformation of one curve to another. Despite its simplicity, when viewed as "curve shortening," it is connected to two deep and decidedly non-obvious theorems: the existence of simple, closed geodesics on a closed surface, and the recently settled Poincaré conjecture. Exploring this connection elucidates the rich interplay between continuous and discrete geometry.

Godfried Toussaint (McGill Univ. and Harvard) [view bio]

The Geometry of Musical Rhythm

Many problems concerning the theory and technology of musical rhythm are fundamentally geometric in nature. Such problems include measuring the similarity and complexity of rhythms, as well as the automatic generation of 'good' rhythms. The interaction between computational geometry and music yields new insights into the theories of rhythm as well as new problems for research in several areas, ranging from computational geometry in computer science to music theory, music perception, and musicology. Recent results on the geometric and computational aspects of rhythm are reviewed, connections to established areas of computer science, mathematics, statistics, computational biology, and crystallography are pointed out, and some open problems are discussed. Rhythm is considered from the symbolical point of view, and no knowledge of music is expected of the audience.

Anna Lubiw (Univ. of Waterloo and MIT) [view bio]

Finding Shortest Paths

We will begin by reviewing algorithms for some geometric shortest path problems, such as finding shortest paths among obstacles in the plane, and finding shortest paths on terrains like the Earth's surface (which, as any bicyclist knows, should not be modelled as a flat plane).

The rest of the talk will be on extensions and variations of these problems. We will look at some touring problems, where you want to visit certain sites with the shortest possible route. In general this is the Travelling Salesman Problem, which is hard, but there are more tractable versions of the problem with such colourful names as the Safari Problem, the Zoo-keeper Problem, and the Watch-man Route Problem.

We will also look at some problems of finding shortest paths on terrains when there are constraints about slope. For example, is there a route from A to B that allows you to coast downhill on your bicycle the whole way? And what if you're afraid of steep hills?

Jack Snoeyink (UNC Chapel Hill) [view bio]

Exploring the Geometry of Molecular Interactions

The models used in structural molecular biology for protein folding and drug design are surprisingly geometric, and many of the questions that they ask, such as "how many unsatisfied hydrogen bond donors are found in the core of a proposed protein structure" are approached by developing geometric algorithms. This tutorial will introduce problems related to hydrogen bond geometries, and show how the exponentially-increasing number of known native structures, and the ability to modify structure prediction code to make new "decoy" structures gives a path for computational experiments and validation.

Gill Barequet (Technion and Tufts University) [view bio]

Half-a-Century of Counting Polycubes and Estimating their Growth Rate

A d-dimensional polycube of size n is a (d-1)-face-connected set of n cubes in d dimensions. Among many interesting questions related to polycubes, one can ask how we can count them efficiently (say, for specific values of n and d), and, for a fixed dimension d, what the asymptotic growth rate of d-dimensional polycubes is. In the past 50 years there have been two (sometimes parallel) research tracks of these questions: one in the mathematical literature and one in the statistical-physics literature. In this talk I will attempt to provide an overview of both tracks.

Nancy M. Amato (Texas A&M University) [view bio]

Randomized Motion Planning: From Intelligent CAD to Group Behaviors to Protein Folding

Motion planning arises in many application domains such as computer animation (digital actors), mixed reality systems and intelligent CAD (virtual prototyping and training), and even computational biology and chemistry (protein folding and drug design). Surprisingly, a single class of planners, called probabilistic roadmap methods (PRMs), have proven effective on problems from all these domains. Strengths of PRMs, in addition to versatility, are simplicity and efficiency, even in high-dimensional configuration spaces.

In this talk, we describe the PRM framework and give an overview of several PRM variants developed in our group. We describe in more detail our work related to virtual prototyping, group behaviors, and protein folding. For virtual prototyping, we show that in some cases a hybrid system incorporating both an automatic planner and haptic user input leads to superior results. For group behaviors, we describe new PRM-based techniques for herding, pursuit/evasion and evacuation planning. Finally, we describe our application of PRMs to simulate molecular motions, such as protein and RNA folding. More information regarding our work, including movies, can be found at

Roberto Tamassia (Brown University) [view bio]

Graph Drawing and Information Visualization

Information visualization is increasingly used in tools for analyzing data in business, engineering, and scientific applications. Constructing effective visual representations of graphs and related combinatorial structures presents significant algorithmic and user interface challenges. In this talk, we survey fundamental techniques for drawing general graphs as well as specialized methods for drawing trees, planar graphs, and directed graphs. We discuss combinatorial and geometric concepts related to graph embedding and address computational issues associated with layout optimization. We also present applications of graph drawing methods to the visualization of security and privacy in computer systems and networks.

Matthew T. Dickerson (Middlebury College) [view bio]

Understanding Voronoi Diagrams as Lower Envelopes

Voronoi Diagrams are one of the most important objects of study in the field of computational geometry. They are a surprisingly simple geometric concept, and yet they let appear in a variety of different and diverse applications and contexts including: astronomy and physics, chemistry and the study of crystals, modeling rainfall, and archaeology. They also can be extended in countless different interesting and non-trivial ways. This presentation will explore a geometric understanding of 2D Voronoi diagrams by looking at collections of 3D surfaces that defined distances.