Search
Close this search box.

Minimum Enclosing Disc with Polygonal Obstacles

Abstract

Minimum Enclosing Disc with Polygonal Obstacles

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 & Links

Related Papers

  • Dan HalperinMicha 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

Contacts

Chaim Linhart

Yair Oz - Webcreator

Contact

Skip to content