 |
 |
 |
 |
| Molecules | Fonts | Motion Planning | Unfolding |
 |
 |
 |
 |
| Manufacturing | Probability | Vertex Enumeration | Graph Drawing |
|
|
|
|
|
| Molecules | Fonts | Motion Planning | Unfolding |
|
|
|
|
|
| Manufacturing | Probability | Vertex Enumeration | Graph Drawing |
 |
Molecular ReconfigurationIn 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. |
Font DesignIn 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. |
 |
 |
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.
|
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. |
  |
 |
Geometric Problems in ManufacturingThere 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. |
Probabilistic AnalysisWe 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. |
 |
 |
Vertex EnumerationThe 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 DrawingWe study the layout of graphs and diagrams. For example, the
picture
here illustrates a 3-dimensional orthogonal grid layout of a graph.
|
 |
|
|
|
|
|
|
|
|
|