On Isolating Points Using Disks

Matt Gibson; Gaurav Kanade; Kasturi Varadarajan

doi:10.1007/978-3-642-23719-5_6

Back

Book chapter

Peer reviewed

On Isolating Points Using Disks

Matt Gibson, Gaurav Kanade and Kasturi Varadarajan

Algorithms – ESA 2011, pp.61-69

Lecture Notes in Computer Science, Springer Berlin Heidelberg

2011

DOI: 10.1007/978-3-642-23719-5_6

View Online

Abstract

In this paper, we consider the problem of choosing disks (that we can think of as corresponding to wireless sensors) so that given a set of input points in the plane, there exists no path between any pair of these points that is not intercepted by some disk. We try to achieve this separation using a minimum number of a given set of unit disks. We show that a constant factor approximation to this problem can be found in polynomial time using a greedy algorithm. To the best of our knowledge we are the first to study this optimization problem.

Approximation Algorithm

Greedy Algorithm

Intersection Graph

Unit Disk

Wireless Sensor Network

Details

Title: Subtitle: On Isolating Points Using Disks
Creators: Matt Gibson - University of Iowa
Gaurav Kanade - University of Iowa
Kasturi Varadarajan - University of Iowa
Resource Type: Book chapter
Publication Details: Algorithms – ESA 2011, pp.61-69
Publisher: Springer Berlin Heidelberg; Berlin, Heidelberg
Series: Lecture Notes in Computer Science
DOI: 10.1007/978-3-642-23719-5_6
eISSN: 1611-3349
ISSN: 0302-9743
Language: English
Date published: 2011
Academic Unit: Computer Science
Record Identifier: 9984259406002771

Metrics

7 Record Views