Question

Let's consider a long, quiet country road with houses scattered very sparsely along it. (We can picture the road as a long line segment, with an eastern endpoint and a western endpoint.) Further, let's suppose that despite the bucolic setting, the residents of all these houses are avid cell phone users. You want to place cell phone base stations at certain points along the road, so that every house is within four miles of one of the base stations. Give an efficient algorithm that achieves this goal, using as few base stations as possible.

Answer 1

Answer:

Follows are the solution to these question:

Explanation:

A simple gullible algorithm is present. Let h mark the house to the left. Then we put a base station about 4 kilometers to the right. Now delete and repeat all the houses protected by this base station. In this algorithm, they can simply be seen to position baselines at b1, . . , bk as well as other algorithms (which may be an optimum algorithm) at $b'_{1}, \ . . . . . . ,b'_{k'}$  and so on. (from left to right)   $b_1 \geq b'_{1},\ \ b_2 \geq b'_{2}$ That's why $k \leq k'$.