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 |

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.