Please use this identifier to cite or link to this item:
https://doi.org/10.1016/j.jda.2003.12.003
| Title: | Packing two disks into a polygonal environment | Authors: | Bose, P. Morin, P. Vigneron, A. |
Keywords: | Computational geometry Disk packing Origami |
Issue Date: | 2004 | Citation: | Bose, P.,Morin, P.,Vigneron, A. (2004). Packing two disks into a polygonal environment. Journal of Discrete Algorithms 2 (3) : 373-380. ScholarBank@NUS Repository. https://doi.org/10.1016/j.jda.2003.12.003 | 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(n log n). This is optimal in the algebraic decision tree model of computation. © 2004 Elsevier B.V. All rights reserved. | Source Title: | Journal of Discrete Algorithms | URI: | http://scholarbank.nus.edu.sg/handle/10635/39351 | ISSN: | 15708667 | DOI: | 10.1016/j.jda.2003.12.003 |
| Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.