2004-09-01
Packing two disks into a polygonal environment
Publication
Publication
Journal of Discrete Algorithms , Volume 2 - Issue 3 p. 373- 380
We consider the following problem. Given a 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 any input, is O(n log n). This is optimal in the algebraic decision tree model of computation.
| Additional Metadata | |
|---|---|
| , , | |
| doi.org/10.1016/j.jda.2003.12.003 | |
| Journal of Discrete Algorithms | |
| Organisation | School of Computer Science |
|
Bose, P, Morin, P, & Vigneron, A. (Antoine). (2004). Packing two disks into a polygonal environment. Journal of Discrete Algorithms, 2(3), 373–380. doi:10.1016/j.jda.2003.12.003
|
|