question is :

State the Optimal Substructure Property for the Highway Cell Tower Problem in terms of the

algorithm PositionTowers. You are not required to prove whether the property holds.

Hint: Let P0 = P n [t1 5; t1 + 5], i.e., P0 is the set of all points in P not covered by t1, where t1

denotes the rst tower added to T by the algorithm PositionTowers.

A rural highway in northern Manitoba does not currently have cell service. A telecommunications provider plans to install cell towers along the highway to provide service to houses along the road, such that each house is within 5 km of a new tower. To keep costs low, the goal is to install as few towers as possible. Suppose that the position of each house or tower along the highway is represented by a point in R+ that corresponds to its the distance from the start of the highway. start of highway 4. 5 k Figure 1: Example. The positions of houses along the highway are represented by the set of dark-coloured points P-p,... ,Pe^ on the line. The positions of towers on the highway are represented by the set of light-coloured points T -[ti,t2,t3) on the line. Each tower covers a radius of 5 km, denoted by a shaded disk. Each point in P is covered by a tower in T. Note that the set T illustrated above is not the solution returned by the algorithm PositionTowers on input P. HIGHWAY CELL TOWER PROBLEM INPUT: a set of n points P-in, 'Pn} in R+ PROBLEM: Find a set of points T {ti, , tm} n R+ such that Tl is minimized and for each point pi P there is some point tj T such that lpi - tjl (tm+5) return T