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 worst case input, is O(n log n). This is optimal in the algebraic decision tree model of computation.
| Original language | English (US) |
|---|---|
| Title of host publication | Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings |
| Editors | Jie Wang |
| Publisher | Springer Verlag |
| Pages | 142-149 |
| Number of pages | 8 |
| ISBN (Print) | 9783540424949 |
| State | Published - 2001 |
| Externally published | Yes |
| Event | 7th Annual International Conference on Computing and Combinatorics, COCOON 2001 - Guilin, China Duration: Aug 20 2001 → Aug 23 2001 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 2108 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Other
| Other | 7th Annual International Conference on Computing and Combinatorics, COCOON 2001 |
|---|---|
| Country/Territory | China |
| City | Guilin |
| Period | 08/20/01 → 08/23/01 |
Bibliographical note
Publisher Copyright:© Springer-Verlag Berlin Heidelberg 2001.
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science