Journal article
On isolating points using unit disks
Journal of computational geometry, Vol.7(1), pp.540-557
12/01/2016
DOI: 10.20382/jocg.v7i1a22
Abstract
Given a set of points in the plane and a set of disks which separate the points, we consider the problem of selecting a minimum size subset of the disks such that any path between any pair of points is intersected by at least one of the selected disks. We present a (9 + epsilon)-approximation algorithm for this problem and show that it is NP-complete even if all disks have unit radius and no disk contains any points. Using a similar reduction, we further show that the Multiterminal Cut problem [9] remains NP-complete on unit disk graphs. Lastly, we prove that removing a minimum subset of a collection of unit disks, such that the plane minus the arrangement of the remaining disks consists of a single connected region is also NP-complete.
Details
- Title: Subtitle
- On isolating points using unit disks
- Creators
- Matt Gibson - Univ Texas San Antonio, Dept Comp Sci, San Antonio, TX 78249 USAGaurav Kanade - University of IowaRainer Penninger - University of BonnKasturi Varadarajan - University of IowaIvo Vigan - CUNY, Grad Ctr, Dept Comp Sci, New York, NY USA
- Resource Type
- Journal article
- Publication Details
- Journal of computational geometry, Vol.7(1), pp.540-557
- DOI
- 10.20382/jocg.v7i1a22
- ISSN
- 1920-180X
- eISSN
- 1920-180X
- Publisher
- Carleton Univ, Dept Mathematics & Statistics
- Number of pages
- 18
- Grant note
- 0915543; 1017539 / National Science Foundation; National Science Foundation (NSF)
- Language
- English
- Date published
- 12/01/2016
- Academic Unit
- Computer Science
- Record Identifier
- 9984411093802771
Metrics
10 Record Views