Connecting a Set of Circles with Minimum Sum of Radii

We consider the problem of assigning radii to a given set of points in the plane, such that the resulting set of circles is connected, and the sum of radii is minimized. We show that the problem is polynomially solvable if a connectivity tree is given. If the connectivity tree is unknown, the proble...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2016-12
Main Authors: Erin Wolf Chambers, Fekete, Sándor P, Hoffmann, Hella-Franziska, Marinakis, Dimitri, Mitchell, Joseph S B, Srinivasan, Venkatesh, Stege, Ulrike, Whitesides, Sue
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Lower bounds
Mathematical analysis
Polynomials
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the problem of assigning radii to a given set of points in the plane, such that the resulting set of circles is connected, and the sum of radii is minimized. We show that the problem is polynomially solvable if a connectivity tree is given. If the connectivity tree is unknown, the problem is NP-hard if there are upper bounds on the radii and open otherwise. We give approximation guarantees for a variety of polynomial-time algorithms, describe upper and lower bounds (which are matching in some of the cases), provide polynomial-time approximation schemes, and conclude with experimental results and open problems.
ISSN:2331-8422