I am trying to design an algorithm for optimal sensor placement in a given area.

After doing some research I found the Art Gallery Problem. However, this problem assumes that the guards can see all the way to the perimeter from their positions, which is not the case with sensors (sensors have a range). Is it possible to solve the optimal sensor placement problem by mapping it to an art gallery problem, and trying some recursive solution?

I would be grateful if someone could throw some light on this question or guide me to appropriate resource.

1 Answer 1


As you correctly say yourself, the art gallery problem is not a good it because it doesn't have the notion of limited distance. It sounds like what you're trying to do can be mapped to the set cover problem. You can discretize the room into a set of places. For each place where you could put down a sensor, you can map it to the set of places that the sensor can sense. The question is then: what is the minimal number of such sets necessary to cover the whole room?

Given this mapping, you can use one of the many algorithms for set cover, for example the greedy algorithm (pick the set that covers the largest number of not-yet-covered places, iterate until everything is covered).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.