Packing two disks into a polygonal environment

Prosenjit Bose; Pat Morin; Antoine Vigneron

doi:10.1016/j.jda.2003.12.003

Packing two disks into a polygonal environment

Prosenjit Bose, Pat Morin^*, Antoine Vigneron

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

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.

Original language	English (US)
Pages (from-to)	373-380
Number of pages	8
Journal	Journal of Discrete Algorithms
Volume	2
Issue number	3
DOIs	https://doi.org/10.1016/j.jda.2003.12.003
State	Published - Sep 2004
Externally published	Yes

Keywords

Computational geometry
Disk packing
Origami

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/j.jda.2003.12.003

Cite this

@article{d89f418fcbd04c1db88a898a7c87c491,

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 any input, is O(n log n). This is optimal in the algebraic decision tree model of computation.",

keywords = "Computational geometry, Disk packing, Origami",

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

year = "2004",

month = sep,

doi = "10.1016/j.jda.2003.12.003",

language = "English (US)",

volume = "2",

pages = "373--380",

journal = "Journal of Discrete Algorithms",

issn = "1570-8667",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - Packing two disks into a polygonal environment

AU - Bose, Prosenjit

AU - Morin, Pat

AU - Vigneron, Antoine

PY - 2004/9

Y1 - 2004/9

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 any 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 any input, is O(n log n). This is optimal in the algebraic decision tree model of computation.

KW - Computational geometry

KW - Disk packing

KW - Origami

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

U2 - 10.1016/j.jda.2003.12.003

DO - 10.1016/j.jda.2003.12.003

M3 - Article

AN - SCOPUS:10644263691

SN - 1570-8667

VL - 2

SP - 373

EP - 380

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

IS - 3

ER -

Packing two disks into a polygonal environment

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this