Abstract | ||
---|---|---|
The stage illumination problem presented by Urrutia in 1992 is one of illumination problems, which uses floodlights for illuminating
a stage. The problem asks whether or not it is possible to rotate given floodlights around their apexes so as to obtain a
final configuration such that a given stage is completely illuminated. The problem for finding a polynomial time algorithm
for this problem or proving NP-hardness of this problem was open. This paper shows that it is NP-complete even with some restrictions.
|
Year | DOI | Venue |
---|---|---|
1998 | 10.1007/978-3-540-46515-7_12 | JCDCG |
Keywords | Field | DocType |
stage illumination problems | Discrete mathematics,Rotation,Computer science,Illumination problem,Algorithm,Problem complexity,Time complexity,Completeness (statistics) | Conference |
Volume | ISSN | ISBN |
1763 | 0302-9743 | 3-540-67181-1 |
Citations | PageRank | References |
5 | 0.82 | 1 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hiro Ito | 1 | 290 | 39.95 |
Hideyuki Uehara | 2 | 54 | 12.14 |
Mitsuo Yokoyama | 3 | 66 | 9.51 |