# 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.

#### References

- A. Bottino, A. Laurentini "Optimal positioning of sensors in 2D". Proc. 9th Iberoamerican Congress on Pattern Recognition, Puebla (Mexico), October 26-29, 2004
- J.C. Culberson and R.A. Reckhow,” Covering polygons is hard,” J Algorithms , Vol.17, pp. 2-44,1994
- T. Danner and L.E. Kavraki,” Randomized planning for short inspections paths,” IEEE Int. Conf. On Robotics and Automation,April 2002, pp. 971-976
- S.Eidenbenz, C. Stamm and P. Widmayer,“ Inapproximability results for guarding polygons and terrains,” Algorithmica, Vol.31, pp.79-113, 2001
- H. Gonzales-Banos and J-C. Latombe,” A randomised art gallery algorithm for sensor placement,” ACM SCG'01, June3-5,2001
- H. Gonzales-Banos and J-C. Latombe.”Planning robot motion for range-image acquisition and automatic 3D model construction,” Proc. AAAI Fall Symposyum Series, 1998
- G. D. Kazakakis, and A.A. Argyros, “Fast positioning of limited visibility guards for inspection of 2D workspaces,” Proc. 2002 IEEE/RSJ Intl. Conf. On Intelligent Robots and Systems, pp.2843-2848, October 2002
- A.Laurentini,”Guarding the walls of an art gallery,” The Visual Computer, vol.15, pp.265-278, 1999
- T.S. Newman and A.K. Jain, “A survay of automated visual inspection,” Comput. Vis. Image Understand. , vol.61, no.2, pp.231-262, 1995
- J. O'Rourke and K.J. Supowit, “Some NP-hard polygon decomposition problems,”IEEE Trans IT, Vol.29, no.2, pp.181-190, March 1983
- J. O'Rourke , Art gallery theorems and algorithms, Oxford University Press, New York,1987
- P. Oestergard, “A fast algorithm for the maximum clique problem,”Discrete Applied Mathematics,Vol.120, pp.197-207, 2002
- J.R.Sack and S.Suri,”An optimal algorithm for detecting weak visibility of a polygon,” IEEE Trans. on Computers,Vol.39, pp.1213-1219, 1990
- T. Shermer, “Recent results in art galleries,” IEEE Proc. Vol. 80, pp.1384-1399, 1992
- W.R.Scott and G.Roth,”View planning for Automated Three-Dimensional Object Reconstruction and Inspection,” ACM Comput. Surveys,Vol.35, No.1, March 2003, pp.64-96
- K.A. Tarabanis, P.K. Allen, and R. Y. Tsai, “ A survey of sensor planning in computer vision,” ,” IEEE Trans. Robot. and Automat., vol. 11, no. 1 , pp. 86 -104, 1995
- J. Urrutia, "Art Gallery and Illumination Problems" Handbook on Computational Geometry, Elsevier Science Publishers, J.R. Sack and J. Urrutia eds. pp. 973-1026, 2000.
- in a graph,” Operations Research Letters,Vol.21, pp.

#### 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