Abstract | ||
---|---|---|
The Art Gallery Problem is aiming at nding the minimum number of guards to cover a gallery. In this paper we consider the problem of covering a gallery with holes. The guards are required to cover a gallery that is represented as a simple polygon with n vertices and h holes. We present a robust and fast algorithm to compute a small number of vertex guards in such polygons, which runs in O (n log n) time and uses O (n) storage. The proposed algorithm is not only offering a better performance in terms of computational cost but also ease in implementation. Simulation results demonstrate the ef ciency, robustness, and potential of the proposed algorithm in motion planning systems. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1109/ICSMC.2004.1398421 | 2004 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN & CYBERNETICS, VOLS 1-7 |
Keywords | Field | DocType |
art gallery, polygons with holes, vertex guards, triangulation, 3-coloring principle, motion planning | Motion planning,Art gallery problem,Polygon,Mathematical optimization,Vertex (geometry),Control theory,Computer science,Computational geometry,Algorithm,Robustness (computer science),Simple polygon,Mobile robot | Conference |
ISSN | Citations | PageRank |
1062-922X | 1 | 0.37 |
References | Authors | |
5 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ashraf Elnagar | 1 | 115 | 21.22 |
Leena Lulu | 2 | 17 | 4.11 |