Minimum Enclosing Disc with Polygonal Obstacles
![[Minimum Enclosing Disc]](disc.gif)
Abstract
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 Ken Goldberg,
The 2-Center Problem with Obstacles
Journal of Algorithms, 42: 109-134, 2002 [link] [bibTex]
A preliminary version appeared in Proceedings of the 16th ACM Symposium on Computational Geometry (SoCG), 80-90, Hong Kong, 2000 [link] [bibtex]
Links
- Chaim Linhart's homepage - with a Java applet which demonstrates the above problem.
Contact
Chaim Linhart | ![]() |
![]() |