On Isolating Points Using Unit Disks
| dc.contributor.author | Gibson, Matthew | |
| dc.contributor.author | Kanade, Gaurav | |
| dc.contributor.author | Penninger, Rainer | |
| dc.contributor.author | Varadarajan, Kasturi | |
| dc.contributor.author | Vigo, Ivo | |
| dc.date.accessioned | 2021-12-07T21:02:47Z | |
| dc.date.available | 2021-12-07T21:02:47Z | |
| dc.date.issued | 2016 | |
| dc.description.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. | en_US |
| dc.description.department | Computer Science | en_US |
| dc.identifier.issn | 1920-180X | |
| dc.identifier.uri | https://hdl.handle.net/20.500.12588/760 | |
| dc.language.iso | en_US | en_US |
| dc.relation.ispartofseries | Journal of Computational Geometry;Vol. 7 No. 1 | |
| dc.rights | Attribution 3.0 United States | * |
| dc.rights.uri | http://creativecommons.org/licenses/by/3.0/us/ | * |
| dc.title | On Isolating Points Using Unit Disks | en_US |
| dc.type | Article | en_US |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- 3026-Article PDF-7897-1-10-20210226.pdf
- Size:
- 638.85 KB
- Format:
- Adobe Portable Document Format
- Description:
License bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- license.txt
- Size:
- 1.86 KB
- Format:
- Item-specific license agreed upon to submission
- Description: