Please use this identifier to cite or link to this item:

Packing two disks into a polygonal environment

Authors Bose, Prosenjit
Morin, Pat
Vigneron, Antoine
Issue Date 2001-02-15
Source Proceedings 7th annual international computing & combinatorics conference (2001), LNCS, v. 2108, 2001, p. 142-149
Summary We consider the following problem. Given a simple polygon P, possibly with holes, and having n vertices, compute a pair of equal radius disks that do not intersect each other, are contained in P, and whose radius is maximized. Our main result is a simple randomized algorithm whose expected running time, on worst case input, is O(nlogn).
Language English
Format Technical report
Files in this item:
File Description Size Format
200102.pdf 205.59 kB Adobe PDF