Packing two disks into a polygonal environment |
| |
Authors: | Prosenjit Bose Pat Morin Antoine Vigneron |
| |
Affiliation: | a School of Computer Science, Carleton University, Canada;b Department of Computer Science, University of Singapore, Singapore |
| |
Abstract: | 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(nlogn). This is optimal in the algebraic decision tree model of computation. |
| |
Keywords: | Disk packing Computational geometry Origami |
本文献已被 ScienceDirect 等数据库收录! |
|