Name
Abstract | ||
|---|---|---|
The Art Gallery Problem is the problem of determining the number of observers necessary to cover an art gallery room such that every point is seen by at least one observer. This problem is well known and has a linear solution for the 2 dimensional case, but little is known in the 3-D case. In this paper we present a polynomial time solution for the 3-D version of the Art Gallery problem. Because the problem is NP-hard, the solution presented is an approximation, and we present the bounds to our solution. Our solution uses techniques from computational geometry, graph coloring and set coverage. A complexity analysis is presented for each step and an analysis of the overall quality of the solution is given |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1109/ACV.1996.572004 | WACV |
Keywords | DocType | ISBN |
3-d case,np-hard,3-d version,set coverage,computational geometry,polynomial time,graph colouring,computational complexity,computer vision,linear solution,art gallery problem,graph coloring,observers placing,polynomial time solution,polyhedral terrain,complexity analysis,dimensional case,2 dimensional,geometry,telephony,np hard,digital elevation models,national security,polynomials,art | Conference | 0-8186-7620-5 |
Citations | PageRank | References |
7 | 3.43 | 7 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maurício Marengoni | 1 | 96 | 19.02 |
| Allen Hanson | 2 | 211 | 33.75 |
| Ramesh K. Sitaraman | 3 | 1928 | 141.68 |
| Bruce A. Draper | 4 | 2001 | 207.57 |