HKUST Library Institutional Repository Banner

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 SizeFormat
200102.pdf205KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.