|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/684
|
| Title: | Packing two disks into a polygonal environment |
| Authors: | Bose, Prosenjit
Morin, Pat
Vigneron, Antoine |
| Keywords: | Randomized algorithm
Disk packing
Polygonal environment |
| Issue Date: | 15-Feb-2001 |
| Citation: | Proceedings 7th annual international computing & combinatorics conference (2001), LNCS, vol. 2108, p. 142-149 |
| Series/Report no.: | HKUST Theoretical Computer Science Center Research Report ; HKUST-TCSC-2001-02 |
| Abstract: | We consider the following problem. Given a simple 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(nlogn). |
| URI: | http://hdl.handle.net/1783.1/684 |
| Appears in Collections: | CSE TCSC Research Reports
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| 200102.pdf | | 205Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
