Optimizing Wireless Internet Coverage for Houses: A Greedy Algorithm Approach

[evinda]

Hello! (Wave)

We consider a long country road with $n$ houses placed along of it (we think of the road as a big line segment). We want to put antenna of wireless internet in some places of the road so that we cover with signal all the houses. Each antenna has a range of $k$ meters and can cover as many houses are in its range. I want to describe a greedy algorithm that achieves this goal using the minimum number of antenna. I also want to compute the complexity and prove the correctness of the greedy algorithm. (The input of the algorithm is an array $A[1 \dots n]$, that contains the distances of the houses in an increasing order from the west side of the road. The output of the algorithm will be the number of antenna that were used in total.)

Can you give me a hint what we could do? (Thinking)

 

[evinda]

I have thought of the following algorithm:

1. We put an antenna $k$ meters east of the westernmost house.
2. We continue to the east, by placing an antenna $k$ meters east of the first house the distance of which from the previous antenna is greater than $k$. We stop when there are no remaining houses more than $k$ meters east of the last antenna that we put or when the distance of the last antenna that we put from the easternmost house is smaller than $k$.
3. If the easternmost house is more than $5$ meters away from the last antenna that we put, we put an antenna at this house.

Is it correct? (Thinking)

 

[I like Serena]

I have thought of the following algorithm:

1. We put an antenna $k$ meters east of the westernmost house.
2. We continue to the east, by placing an antenna $k$ meters east of the first house the distance of which from the previous antenna is greater than $k$. We stop when there are no remaining houses more than $k$ meters east of the last antenna that we put or when the distance of the last antenna that we put from the easternmost house is smaller than $k$.
3. If the easternmost house is more than $5$ meters away from the last antenna that we put, we put an antenna at this house.

Is it correct? (Thinking)

I've looked up the greedy algorithm and I think your approach is correct.
Where did you get the specific $5$ meters though? Shouldn't it be $k$ meters? (Wondering)

 

[evinda]

I've looked up the greedy algorithm and I think your approach is correct.
Where did you get the specific $5$ meters though? Shouldn't it be $k$ meters? (Wondering)

Oh yes, that's a typo... I meant $k$... (Nerd)