Packing two disks into a polygonal environment

Prosenjit Bose, Pat Morin*, Antoine Vigneron

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Pages (from-to)373-380
Number of pages8
JournalJournal of Discrete Algorithms
Volume2
Issue number3
DOIs
StatePublished - Sep 1 2004

Keywords

  • Computational geometry
  • Disk packing
  • Origami

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Packing two disks into a polygonal environment'. Together they form a unique fingerprint.

Cite this