Packing two disks into a polygonal environment

Prosenjit Bose; Pat Morin; Antoine Vigneron

Packing two disks into a polygonal environment

Prosenjit Bose, Pat Morin, Antoine Vigneron

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Cite this

Bose, P., Morin, P., & Vigneron, A. (2001). Packing two disks into a polygonal environment. In J. Wang (Ed.), Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings (pp. 142-149). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2108). Springer Verlag.

Bose, Prosenjit ; Morin, Pat ; Vigneron, Antoine. / Packing two disks into a polygonal environment. Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings. editor / Jie Wang. Springer Verlag, 2001. pp. 142-149 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9dc63238815e48fea864555bdc451d72,

title = "Packing two disks into a polygonal environment",

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.",

author = "Prosenjit Bose and Pat Morin and Antoine Vigneron",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 7th Annual International Conference on Computing and Combinatorics, COCOON 2001 ; Conference date: 20-08-2001 Through 23-08-2001",

year = "2001",

language = "English (US)",

isbn = "9783540424949",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "142--149",

editor = "Jie Wang",

booktitle = "Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings",

address = "Germany",

}

Bose, P, Morin, P & Vigneron, A 2001, Packing two disks into a polygonal environment. in J Wang (ed.), Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2108, Springer Verlag, pp. 142-149, 7th Annual International Conference on Computing and Combinatorics, COCOON 2001, Guilin, China, 08/20/01.

Packing two disks into a polygonal environment. / Bose, Prosenjit; Morin, Pat; Vigneron, Antoine.
Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings. ed. / Jie Wang. Springer Verlag, 2001. p. 142-149 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2108).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Packing two disks into a polygonal environment

AU - Bose, Prosenjit

AU - Morin, Pat

AU - Vigneron, Antoine

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84944096670&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84944096670

SN - 9783540424949

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 142

EP - 149

BT - Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings

A2 - Wang, Jie

PB - Springer Verlag

T2 - 7th Annual International Conference on Computing and Combinatorics, COCOON 2001

Y2 - 20 August 2001 through 23 August 2001

ER -

Packing two disks into a polygonal environment

Abstract

Publication series

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this