Ponencia
On the barrier-resilience of arrangements of ray-sensors
Autor/es | Kirkpatrick, David
Yang, Boting Zilles, Sandra |
Coordinador/Director | Díaz Báñez, José Miguel
Garijo Royo, Delia Márquez Pérez, Alberto Urrutia Galicia, Jorge |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada II |
Fecha de publicación | 2013 |
Fecha de depósito | 2017-05-18 |
Publicado en |
|
Resumen | Given an arrangement A of n sensors and two points s and t in the plane, the barrier resilience of A with respect to s and t is the minimum number
of sensors whose removal permits a path from s to t such that the path ... Given an arrangement A of n sensors and two points s and t in the plane, the barrier resilience of A with respect to s and t is the minimum number of sensors whose removal permits a path from s to t such that the path does not intersect the coverage region of any sensor in A. When the surveillance domain is the entire plane and sensor coverage regions are unit line segments, even with restricted orientations, the problem of determining the barrier resilience is known to be NP-hard. On the other hand, if sensor coverage regions are arbitrary lines, the problem has a trivial linear time solution. In this paper, we give an O(n2m) time algorithm for computing the barrier resilience when each sensor coverage region is an arbitrary ray, where m is the number of sensor intersections. |
Cita | Kirkpatrick, D., Yang, B. y Zilles, S. (2013). On the barrier-resilience of arrangements of ray-sensors. En XV Spanish Meeting on Computational Geometry, Sevilla. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
On the barrier-resilience of ... | 830.2Kb | [PDF] | Ver/ | |