Connecting a set of circles with minimum sum of radii

DOI10.1007/978-3-642-22300-6_16zbMATH Open1380.05113arXiv1105.0791OpenAlexW2623275761MaRDI QIDQ1699280FDOQ1699280

Authors: Sándor P. Fekete, Hella-Franziska Hoffmann, Dimitri Marinakis, Joseph S. B. Mitchell, Venkatesh Srinivasan, Ulrike Stege, Erin W. Chambers, Sue Whitesides 

Publication date: 19 February 2018

Published in: Lecture Notes in Computer Science, Computational Geometry (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1105.0791

Recommendations

• Connecting a set of circles with minimum sum of radii
• On the complexity of two circle connecting problems
• Minimum-cost coverage of point sets by disks
• On clustering to minimize the sum of radii
• On Metric Clustering to Minimize the Sum of Radii

zbMATH Keywords

approximationintersection graphsNP-hardnessupper and lower boundsconnectivity problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22) Connectivity (05C40)

Cites Work

• Planar Formulae and Their Uses
• Reverse search for enumeration
• On the hardness of range assignment problems
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Minimum-energy broadcasting in static ad hoc wireless networks
• Polynomial time approximation schemes for base station coverage with minimum total radii
• Algorithms – ESA 2005
• Minimum-cost coverage of point sets by disks
• Approximation of geometric dispersion problems
• Clustering to minimize the sum of cluster diameters
• Augmenting the connectivity of geometric graphs
• Approximation algorithms for clustering to minimize the sum of diameters
• Energy-efficient wireless network design
• Connecting a set of circles with minimum sum of radii
• Title not available (Why is that?)
• Algorithm Theory - SWAT 2004
• The minimum-area spanning tree problem

Cited In (14)

• ``Green barrier coverage with mobile sensors
• A note on minimum-sum coverage by aligned disks
• Title not available (Why is that?)
• Faster algorithms for some optimization problems on collinear points
• Bounded-hop communication networks
• On the bounded-hop range assignment problem
• Existence and hardness of conveyor belts
• Changing of the guards: strip cover with duty cycling
• Range assignment of base-stations maximizing coverage area without interference
• Connecting points using centered disks
• Average case network lifetime on an interval with adjustable sensing ranges
• Connecting a set of circles with minimum sum of radii
• Connecting Cycles for Concentric Circles
• Set it and forget it: approximating the set once strip cover problem

This page was built for publication: Connecting a set of circles with minimum sum of radii

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1699280)