TY - GEN

T1 - Packing two disks into a polygonal environment

AU - Bose, Prosenjit

AU - Morin, Pat

AU - Vigneron, Antoine

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2001.

PY - 2001

Y1 - 2001

N2 - 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 worst case input, is O(n log n). This is optimal in the algebraic decision tree model of computation.

AB - 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 worst case input, is O(n log n). This is optimal in the algebraic decision tree model of computation.

UR - http://www.scopus.com/inward/record.url?scp=84944096670&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84944096670

SN - 9783540424949

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 142

EP - 149

BT - Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings

A2 - Wang, Jie

PB - Springer Verlag

T2 - 7th Annual International Conference on Computing and Combinatorics, COCOON 2001

Y2 - 20 August 2001 through 23 August 2001

ER -