Connecting a Set of Circles with Minimum Sum of Radii

Details Connecting a Set of Circles with Minimum Sum of Radii Connecting a Set of Circles with Minimum Sum of Radii

2011-05-04

arxiv.org/abs/1105.0791v1

Computer Science

Computational Geometry

14 pages, 8 figures, conference version to appear in Proceedings of the 12th Algorithms and Data Structures Symposium (WADS 20

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Connecting a Set of Circles with Minimum Sum of Radii does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Connecting a Set of Circles with Minimum Sum of Radii, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Connecting a Set of Circles with Minimum Sum of Radii will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-689437