Go to  Advanced Search

Approximating barrier resilience and related notions for disk sensors in a two-dimensional plane

Show full item record

Files in this item

Files Size Format Description   View
ubc_2012_fall_chan_david.pdf 981.5Kb Adobe Portable Document Format   View/Open
Title: Approximating barrier resilience and related notions for disk sensors in a two-dimensional plane
Author: Chan, David Yu Cheng
Degree Master of Science - MSc
Program Computer Science
Copyright Date: 2012
Publicly Available in cIRcle 2012-10-17
Abstract: Let A be an arrangement of n sensors constituting a barrier, the resilience of A with respect to two regions S and T, denoted ρ(A,S,T), is defined as the number of sensors in A that must be removed in order for there to be a path from S to T that is not detected by any sensor. Previous work by Bereg and Kirkpatrick proved that a 3-approximation of the resilience could be guaranteed by a polynomial time algorithm when sensors are unit disks in the plane. This was tightened to a 5/3-approximation when S and T are well-separated. In this thesis, we define and analyze a Multi-Path Algorithm (MPA) which improves on these bounds to get approximation ratios of 2 and 1.5 respectively. Additionally, we define a new notion of barrier strength called Dc-Resilience, which is the resilience of the barrier if regions covered by more than c distinct sensors in the original arrangement are treated as inaccessible, in the sense that no part of any path is permitted to intersect with such a region. We consider arrangements of disk sensors with radii in range [1 - ξ, 1] for any 0 ≤ ξ < 1 independent of n. We prove that for any such arrangement and any constant c, the MPA guarantees a constant approximation of the Dc-resilience in time polynomial in n for any constant c. Furthermore, we show that this tightens to a 2-approximation under certain conditions which are usually fulfilled when disk sensors are close to equal size.
URI: http://hdl.handle.net/2429/43455
Scholarly Level: Graduate

This item appears in the following Collection(s)

Show full item record

All items in cIRcle are protected by copyright, with all rights reserved.

UBC Library
1961 East Mall
Vancouver, B.C.
Canada V6T 1Z1
Tel: 604-822-6375
Fax: 604-822-3893