We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
SEARCHING POLYHEDRA BY ROTATING HALF-PLANES.
- Authors
VIGLIETTA, GIOVANNI
- Abstract
THE SEARCHLIGHT SCHEDULING PROBLEM was first studied in 2-dimensional polygons, where the goal is for point guards in fixed positions to rotate searchlights to catch an evasive intruder. Here the problem is extended to 3-dimensional polyhedra, with the guards now boundary segments who rotate half-planes of illumination. After carefully detailing the 3-dimensional model, several results are established. The first is a nearly direct extension of the planar one-way sweep strategy using what filling guards, a generalization that succeeds despite there being no well-defined we call notion in 3-dimensional space of planar "clockwise rotation." Next follow two results: every polyhedron with r > 0 reflex edges can be searched by at most r2 suitably placed boundary guards, whereas just r edguards suffice if the polyhedron is orthogonal. (Mini-mizing the number of guards to search a given polyhedron is easily seen to be NP-hard.) Finally we show that deciding whether a given set of boundary guards has a successful search schedule is strongly NP-hard. A number of peripheral results are proved en route to these central theorems, and several open problems remain for future work.
- Subjects
SEARCHLIGHTS; POLYHEDRA; GENERALIZATION; DIMENSIONAL analysis; NUMBER theory; MATHEMATICAL models
- Publication
International Journal of Computational Geometry & Applications, 2012, Vol 22, Issue 3, p243
- ISSN
0218-1959
- Publication type
Article
- DOI
10.1142/S0218195912500070