mwang@watmath.UUCP (mwang) (11/21/85)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
DATA STRUCTURING SEMINAR
- Tuesday, November 25, 1985.
Dr. Peter Widmayer of Universitat will speak on ``Shor-
test Orthogonal Connections with Orthogonal Obsta-
cles''.
TIME: 12:30 PM
ROOM: MC 5158
ABSTRACT
Consider a set of points in the plane, and a set of
obstacles. The obstacles are polygons with edges
parallel to the coordinate axes. A path between two
points consists of line segments parallel to the coor-
dinate axes, and it is not allowed to pass through any
obstacle. We now have to find shortest paths from a
point to all others, and how to compute a minimum tree
for the set of points.