Placement and orientation of rotating directional sensors

In this paper, we address several problems that arise in the context of rotating directional sensors. Rotating directional sensors (RDS) have a "directional" coverage region that "rotates" at a certain speed. For RDS with fixed given locations, we address three problems with the objective to minimize different functions of the dark time (i.e., uncovered time) of the given points in the area. In addition, we also consider the problem of placement and orientation of the minimum number of given RDS, so as to reduce the dark time of all given points to zero. Finally, we address the barrier coverage problems wherein we wish to place and/or orient the RDS to ensure "detection" of maximum number of intruders who are attempting to cross the monitored area. We prove the addressed problems to be NP-hard; some of the them are showed to be even NP-hard to approximate. We provide approximation algorithms which are easy to decentralize.