1
$\begingroup$

I'm having troubles finding information on how to solve/optimize a problem I'm currently facing, which probably means I'm either approaching it poorly and/or I don't know what to search for.

The question I think I need the answer to: given several sets of possibilities, what is the smallest number of sets I must select to cover the entire range of possibilities? Alternatively, what is the smallest number of cameras I need to have 100% coverage of all points of interest? The latter is the real underlying form of the question, but the former may be an XY problem.

How do I optimize this problem?


My specific scenario is a little complex to describe here, but here's a simplistic scenario that should be sufficiently analogous:

Imagine I have a large facility with many specific places I want to be under the supervision of security cameras ("targets"), and imagine I have a lot of different places I could put cameras ("sentries").

Naturally, each possible sentry position can see some set of targets - some may not be able to see any, some may one see one, but many may see many.

I'm trying to find a way to place the smallest number of cameras to have complete coverage of all the targets. I suspect this will naturally also become a minimum-overlap problem, but does not have to be.


My sets are small enough that I am able to quickly fully enumerate every sentry position and the set of all target positions it can see, which I can either represent (in python) as the set of target indexes (e.g. set([1,3,4])) or a numpy array that's a bitmask of targets viewable (e.g. numpy.array([False,True,False,True,True],dtype=bool)), or another form if another form is more valuable. (Technically, I'm enumerating all sets of targets which are viewable by a single camera, and for every one of those sets there may be multiple camera positions which can see that set, but this difference is immaterial to the end goal).

I know from experience that if I start exhaustively enumerating all combinations of those to find full-coverage sets, even if I aggressively stop searching if I've exceeded my previous-best camera counts, that this will explode too quickly to run.

My end optimization goal is to find the minimum number of cameras. The minimum overlap isn't important (in fact, maximum overlap may be preferred when reasonable), but the number of cameras is the single most-important factor; given the choice between 6 cameras with no overlap and 7 cameras with lots of overlap, the 6 will always be preferred.

$\endgroup$
3
  • 2
    $\begingroup$ Without knowing more about the restrictions to your problem, it sounds an awful lot like the Set cover problem which is NP-hard. $\endgroup$ – Pål GD Feb 1 at 15:58
  • $\begingroup$ Yes! That is exactly it! And of course it's NP-hard... But at least this has given me a place to start; thank you! $\endgroup$ – iAdjunct Feb 1 at 16:26
  • $\begingroup$ @PålGD post your comment as an answer and I’ll accept it (because it indeed the exact right answer) $\endgroup$ – iAdjunct Feb 3 at 3:59
2
$\begingroup$

Without knowing anything about the restrictions to your problem, the general version is Set cover, one of Karp's 21 NP-complete problems.

However, if you know more about the structure of the data, you might be able to get better algorithms, see for example the Art gallery problem, where you are given a polygon, and want to find the minimum number of guards/cameras you should place that cover the entire polygon.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you! The art-gallery-problem may be close to my overall problem, but my computational environment and methods don't support treating the problem that way - though that may change. I tested the Randomized-Rounding method of solving the SCP, then found Meta-RaPS and the latter is working very well for my problem in a very, very reasonable amount of time (10 seconds is significantly better than 2 days). $\endgroup$ – iAdjunct Feb 3 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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