Guarding the walls of an art gallery |
| |
Authors: | Aldo Laurentini |
| |
Affiliation: | (1) Dipartimento di Automatica ed Informatica, Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129 Torino, Italy; E-mail: laurentini@polito.it, IT |
| |
Abstract: | P so that each point of P is seen by at least one guard. We introduce and explore the edge-covering problem; the guards are required to observe the
edges of P; metaphorically the paintings on the walls of the art gallery, and not necessarily every interior point. We compare minimum
edge and interior covers for a given polygon and analyze the bounds and complexity for the edge-covering problem. We also
introduce and analyze a restricted edge covering problem, where full visibility of each edge from at least one guard is required.
For this problem we present an algorithm that computes a set of regions where a minimum set of guards must be located. The
algorithm can also deal with the external visibility of a set of polygons. |
| |
Keywords: | : Computational geometry – Visibility – Illumination – Visual sensor placement – Art gallery problem and theorems – Edge covering |
本文献已被 SpringerLink 等数据库收录! |
|