McGill University - School of Computer Science
Computational Geometry Seminar
Everybody is welcome.
|
DATE:
|
Wednesday, November 19th, 1997
|
|
TIME:
|
12h00 - 13h00
|
|
PLACE:
|
McConnell 320
|
|
TITLE:
|
"The Constrained Minimum Spanning Circle Problem"
|
|
SPEAKER:
|
Prof. Godfried Toussaint, School of Computer Science, McGill University.
|
In this talk we consider constrained versions of the minimax facility
location problem for n customers (points).
In two dimensions we provide an O(n+m) time algorithm for the problem
of constructing the minimum enclosing
circle with center constrained to lie in an m-vertex convex polygon.
This improves the best known solution of O((n+m) log (n+m)) time.
We also show that linearity is preserved even when the polygon
is given as only a set of linear constraints.
Since this result follows from a marriage of the Megiddo-Dyer algorithms for
linear programming and finding smallest enclosing circles,
we review the latter algorithms in some detail.
We also generalize the unconstrained version of the problem
to the surface of a sphere. Here the problem reduces
to finding the smallest spherical cap that contains the
given points. We uncover a curious discontinuity in
the geometric complexity of problems on the sphere.
First we show that the problem
on the entire sphere has complexity Theta(n log n).
Then we show that when the points lie in some
unknown open hemisphere the problem can be solved in O(n) time.
This is joint work with Ferran Hurtado and Vera Sacristan from Barcelona.
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.