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.
@article{hsg-tcpo-02,
author = {Dan Halperin and Micha Sharir and Ken Goldberg},
title = {The 2-Center problem with obstacles},
journal = {Journal of Algorithms},
volume = {42},
number = {1},
year = {2002},
pages = {109--134},
doi = {10.1006/jagm.2001.1194}
}
@inproceedings{hsg-tcpo-00,
author = {Dan Halperin and Micha Sharir and Kenneth Y. Goldberg},
title = {The 2-center problem with obstacles},
booktitle = {Proceedings of the 16th Symposium on Computational Geometry (SoCG)},
year = {2000},
pages = {80-90},
doi = {10.1145/336154.336184}
}