A NEW ART GALLERY ALGORITHM FOR SENSOR LOCATION

Andrea Bottino, Aldo Laurentini

2005

Abstract

Locating sensors in2D can be often modeled as an Art Gallery problem. Unfortunately, this problem is NP-hard, and no finite algorithm, even exponential, is known for its solution. Algorithms able to closely approximate the optimal solution and computationally feasible in the worst case are unlikely to exist. However this is an important problem and algorithms with “good” performance in practical cases are sorely needed. After reviewing the available algorithms, we propose a new sensors location incremental technique. The technique converges toward the optimal solution. It locally refines a starting approximation provided by an integer covering algorithm, where each edge is observed entirely by at least one sensor. A lower bound for the number of sensor, specific of the polygon considered, is used for halting the algorithm, and a set of rules are provided to simplify the problem.

Paper Citation

in Harvard Style

Bottino A. and Laurentini A. (2005). A NEW ART GALLERY ALGORITHM FOR SENSOR LOCATION . In Proceedings of the Second International Conference on Informatics in Control, Automation and Robotics - Volume 2: ICINCO, ISBN 972-8865-30-9, pages 242-249. DOI: 10.5220/0001174002420249

in Bibtex Style

@conference{icinco05,
author={Andrea Bottino and Aldo Laurentini},
title={A NEW ART GALLERY ALGORITHM FOR SENSOR LOCATION},
booktitle={Proceedings of the Second International Conference on Informatics in Control, Automation and Robotics - Volume 2: ICINCO,},
year={2005},
pages={242-249},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001174002420249},
isbn={972-8865-30-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the Second International Conference on Informatics in Control, Automation and Robotics - Volume 2: ICINCO,
TI - A NEW ART GALLERY ALGORITHM FOR SENSOR LOCATION
SN - 972-8865-30-9
AU - Bottino A.
AU - Laurentini A.
PY - 2005
SP - 242
EP - 249
DO - 10.5220/0001174002420249