5
$\begingroup$

I'm doing some work on a problem and I'm finding it difficult to research it with out the actual name of the problem, since the problem I'm working on gives it it's own abstraction.

The problem is this, Given a long straight road S is the set of the locations of houses down the road. For example S = [1,2,3] would be that houses are placed at 1km 2km and 3km from the end of the road.

We have radio towers that cover a range of 1km and we want to place radio towers at locations along the road so that all houses are covered using the minimum number of towers.

I already know the algorithm to do it, however I'm finding it difficult to understand the proof so would really like the formal name for this problem so that I can research it further.

Improve this question
$\endgroup$
1
  • $\begingroup$ there is also a related graph-based formulation of the problem called the "n-center" problem $\endgroup$
    – vzn
    Commented Nov 15, 2014 at 15:47

1 Answer 1

Reset to default
7
$\begingroup$

This general form of problem is a facility location problem. The specific version you're asking about is a covering problem – you have a set of points (the houses) and you're trying to cover them with circles of some radius (the areas that get reception from each tower).

Improve this answer
$\endgroup$

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.