- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Approximating barrier resilience and related notions...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Approximating barrier resilience and related notions for disk sensors in a two-dimensional plane Chan, David Yu Cheng
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.
Item Metadata
Title |
Approximating barrier resilience and related notions for disk sensors in a two-dimensional plane
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
2012
|
Description |
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.
|
Genre | |
Type | |
Language |
eng
|
Date Available |
2012-10-17
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0052170
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2012-11
|
Campus | |
Scholarly Level |
Graduate
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International