ILLUMINATION OF ORTHOGONAL POLYGONS WITH ORTHOGONAL FLOODLIGHTS

Authors
ABELLO J ESTIVILLCASTRO V SHERMER T URRUTIA J
Citation
J. Abello et al., ILLUMINATION OF ORTHOGONAL POLYGONS WITH ORTHOGONAL FLOODLIGHTS, International journal of Computational geometry and applications, 8(1), 1998, pp. 25-38
Citations number
21
Categorie Soggetti
Mathematics,"Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods
Journal title
International journal of Computational geometry and applications → ACNP
ISSN journal
02181959
Volume
8
Issue
1
Year of publication
1998
Pages
25 - 38
Database
ISI
SICI code
0218-1959(1998)8:1<25:IOOPWO>2.0.ZU;2-9
Abstract
We provide the first tight bound for covering an orthogonal polygon wi th n vertices and h holes with vertex floodlights (guards with restric ted angle of vision). In particular, we provide tight bounds for the n umber of orthogonal floodlights, placed at vertices or on the boundary , sufficient to illuminate the interior or the exterior of an orthogon al polygon with holes. Our results lead directly to very simple linear , and thus optimal, algorithms for computing a covering of an orthogon al polygon.