Colloquium Speaker

Speaker: Sue Whitesides
McGill University, Montreal
Topic:Embedding Problems for Paths and Cycles
with Direction Constrained Edges
Date:Tuesday, November 27, 2001
Time:11:00 AM
Place:Gould-Simpson, Room 701

Refreshments will be served in the 7th-floor lobby of Gould-Simpson at 10:45 AM


An "orthogonal shape path" is a sequence of n axis-aligned direction vectors in R^d. To "realize" a shape path means to assign a positive integer length to each element in the sequence so that the resulting orthogonal polygonal curve is non-self-intersecting. Shape cycles may be defined in an analogous way.

We study reachability properties of shape paths. For example, we characterize those shape paths that have realizations that start at the origin and, with an appropriate assignment of lengths to their elements, end at a point with all positive coordinates.

We also characterize those cyclic sequences of axis-aligned direction vectors that can be realized as closed, orthogonal, polygonal curves in R^3.