Prof. David Rappaport, School of Computer Science, Queen's University.
Let S denote a set of non-intersecting translates of the same closed
compact convex
object. We say that two objects a and b from the set Ssee each other
if there exists a straight line segment l with one point in a and one
point in b such that l does not intersect the interior of any
other object in S. We call such a line segment a line of sight.
The visibility graph of S, denoted by Vis(S),
associates a vertex to each object of S, and an edge between two
vertices if
the
associated objects see each other.
We show that Vis(S)
always contains a Hamiltonian path, for translates of a convex
object. We also show that this path can be found
with an efficient algorithm without having to explicitly determine
Vis(S).
Furthermore, we show that every other
edge in the Hamiltonian path can be used to obtain a maximal matching
that is realized by a set of non intersecting lines
of sight.
This information is available at
http://cgm.cs.mcgill.ca/~therese/seminar.
Direct questions, comments, additions to and removals from the mailing list, and
suggestions for speakers to Therese Biedl at
therese@cgm.cs.mcgill.ca.