Packing two disks into a polygonal environment

Prosenjit Bose, Pat Morin, Antoine Vigneron

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-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 languageEnglish (US)
Title of host publicationComputing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings
PublisherSpringer Verlag
Pages142-149
Number of pages8
Volume2108
ISBN (Print)9783540424949
StatePublished - 2001
Externally publishedYes
Event7th Annual International Conference on Computing and Combinatorics, COCOON 2001 - Guilin, China
Duration: Aug 20 2001Aug 23 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2108
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other7th Annual International Conference on Computing and Combinatorics, COCOON 2001
CountryChina
CityGuilin
Period08/20/0108/23/01

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Fingerprint

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

Cite this