Given a set S of points in the plane and a set P of polyons (obstacles),
we wish to find a disc of radius r that covers S and whose center is not
inside one of the polygons in P, as well as to approximate the minimal
r for which there exists such a disc.
Related Papers
Dan Halperin,
Micha Sharir
and K. Goldberg,
The 2-Center Problem with Obstacles (the full version)
Journal of Algorithms vol. 42, 2002, pp. 109-134.
A preliminary version appeared in Proc. 16th ACM Symposium on Computational Geometry, Hong Kong, 2000, 80-90.
[BibTex,Gzipped Postscript]
![[Minimum Enclosing Disc]](../images/disc.gif)
![[Projects Page]](../images/icons/projects.gif){kind=icon}
![[Top]](../images/icons/top.gif){kind=icon}
