Covering and piercing disks with two centers

Heekap Ahn, Sangsub Kim, Christian Knauer, Lena Schlipf, Chansu Shin, Antoine E. Vigneron

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider new versions of the two-center problem where the input consists of a set D of disks in the plane. We first study the problem of finding two smallest congruent disks such that each disk in intersects one of these two disks. Then we study the problem of covering the set D by two smallest congruent disks. We give exact and approximation algorithms for these versions. © 2011 Springer-Verlag.
Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science
PublisherSpringer Nature
Pages50-59
Number of pages10
ISBN (Print)9783642255908
DOIs
StatePublished - 2011

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Covering and piercing disks with two centers'. Together they form a unique fingerprint.

Cite this