# Computational Geometry Research at McGill

 Molecules Fonts Motion Planning Unfolding Manufacturing Probability Vertex Enumeration Graph Drawing

## Molecular Reconfiguration

In chemistry and physics large molecules are often modelled as polygonal linkages. Properties of these molecules can be determined by geometric properties of the underlying linkages. The purpose of this research is to study the combinatorial and algorithmic aspects of polygonal linkages to help further our understanding of how molecules reconfigure themselves.

Godfried Toussaint

## Font Design

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.

Luc Devroye

## Robot Motion Planning

Robotic arms are frequently used in manufacturing plants to perform tasks such as welding, screwing and drilling. Geometric questions in robotic motion planning involve finding efficient motion plans for a given robotic arm and determining what kinds of tasks a given robotic arm can and can not do.

Sue Whitesides

## Unfolding Polytopes

Given a 3-dimensional polytope, how can we cut and unfold it so that it lies in the plane? What if we require that the unfolding not overlap itself? The image on the right shows a polytope and a non-overlapping unfolding of that polytope. These questions have applications in manufacturing and in the design of origamis.

Komei Fukuda

## 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.

Godfried Toussaint

## Probabilistic 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.

Luc Devroye

## 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. For more information see PolytopeBase, an annotated bibliography maintained by former McGill student David Bremner.

David Avis

## Graph Drawing

We study the layout of graphs and diagrams. For example, the picture here illustrates a 3-dimensional orthogonal grid layout of a graph.

Sue Whitesides