Faster Algorithms for some Optimization Problems on Collinear Points
Ahmad Biniaz Prosenjit Bose Paz Carmi Anil Maheshwari J. Ian Munro Michiel Smid

[
    [
    December 30, 2023
=====================


We propose faster algorithms for the following three optimization problems on n collinear points, i.e., points in dimension one. The first two problems are known to be NP-hard in higher dimensions.


	
  * Maximizing total area of disjoint disks: In this problem the goal is to maximize the total area of nonoverlapping disks centered at the points. Acharyya, De, and Nandy (2017) presented an O(n^2)-time algorithm for this problem. We present an optimal Θ(n)-time algorithm.   
	
  * Minimizing sum of the radii of client-server coverage: The n points are partitioned into two sets, namely clients and servers. The goal is to minimize the sum of the radii of disks centered at servers such that every client is in some disk, i.e., in the coverage range of some server. Lev-Tov and Peleg (2005) presented an O(n^3)-time algorithm for this problem. We present an O(n^2)-time algorithm, thereby improving the running time by a factor of Θ(n). 
	
  * Minimizing total area of point-interval coverage: The n input points belong to an interval I. The goal is to find a set of n disks of minimum total area, covering I, such that every disk contains at least one input point. We present an algorithm that solves this problem in O(n^2) time.






§ INTRODUCTION


Range assignment is a well-studied class of geometric optimization problems that arises in wireless network design, and has a rich literature. The task is to assign transmission ranges to a set of given base station antennas such that the resulting network satisfies a given property. The antennas are usually represented by points in the plane. The coverage region of an antenna is usually represented by a disk whose center is the antenna and whose radius is the transmission range assigned to that antenna. In this model, a range assignment problem can be interpreted as the following problem. Given a set of points in the plane, we must choose a radius for each point, so that the disks with these radii satisfy a given property. 

Let P={p_1,…,p_n} be a set of n points in the d-dimensional Euclidean space. A range assignment for P is an assignment of a transmission range r_i⩾ 0 (radius) to each point p_i∈ P.
The cost of a range assignment, representing the power consumption of the network, is defined as
C=∑_ir_i^α for some constant α⩾ 1.
We study the following three range assignment problems on a set of points on a straight-line (1-dimensional Euclidean space).


	
  Problem 1 Given a set of collinear points, maximize the
	total area of nonoverlapping disks centered at these points. The nonoverlapping constraint requires r_i+r_i+1 to be no larger than the Euclidean distance between p_i and p_i+1, for every i∈{1,…,n-1}.
	

	
  Problem 2 Given a set of collinear points that is partitioned into
	two sets, namely clients and servers, the goal is to minimize the sum of the radii of disks centered at the servers such that every client is in some disk, i.e., every client is covered by at least one server.
	

	
  Problem 3 Given a set {p_1,…, p_n} of n points on an interval, find a set D_1,…,D_n of n disks covering the entire interval such that the total area of disks is minimized and for every i the disk D_i contains the point p_i.


In Problem 1 we want to maximize ∑ r_i^2, in Problem 2 we want to minimize ∑ r_i, and in Problem 3 we want to minimize ∑ r_i^2. These three problems are solvable in polynomial time in 1-dimension. Both Problem 1 and Problem 2 are NP-hard in dimension d, for every d ⩾ 2, and both have a PTAS <cit.>. 

Acharyya  <cit.> showed that Problem 1 can be solved in O(n^2) time. Eppstein <cit.> proved that an alternate version of this problem, where the goal is to maximize the sum of the radii, can be solved in O(n^2-1/d) time for any constant dimension d.
Bilò   <cit.> showed that Problem 2 is solvable in polynomial time by reducing it to an integer linear program with a totally unimodular constraint matrix. Lev-Tov and Peleg <cit.> presented an O(n^3)-time algorithm for this problem. They also presented a linear-time 4-approximation algorithm. Alt  <cit.> improved the ratio of this linear-time algorithm to 3. They also presented an O(nlog n)-time 2-approximation algorithm for Problem 2. Chambers  <cit.> studied a variant of Problem 3—on collinear points—where the disks centered at input points; they showed that the best solution with two disks gives a 5/4-approximation.
Carmi  <cit.> studied a similar version of the problem for points in the plane. 



 §.§ Our Contributions

In this paper we study Problems 1-3. In Section <ref>, we present an algorithm that solves Problem 1 in linear time, provided that the points are given in sorted order along the line. This improves the previous best running time by a factor of Θ(n). In Section <ref>, we present an algorithm that solves Problem 2 in O(n^2) time; this also improves the previous best running time by a factor of Θ(n). In Section <ref>, first we present a simple O(n^3) algorithm for Problem 3. Then with a more involved proof, we show how to improve the running time to O(n^2).



§ PROBLEM 1: DISJOINT DISKS WITH MAXIMUM AREA


In this section we study Problem 1: Let P={p_1,…,p_n} be a set of n⩾ 3 points on a straight-line ℓ that are given in sorted order. We want to assign to every p_i∈ P a radius r_i such that the disks with the given radii do not overlap and their total area, or equivalently ∑ r_i^2, is as large as possible. Acharyya  <cit.> showed how to obtain such an assignment in O(n^2) time. We show how to obtain such an assignment in linear time. 


	Given n collinear points in sorted order in the plane, in Θ(n) time, we can find a set of nonoverlapping disks centered at these points that maximizes the total area of the disks.


With a suitable rotation we assume that ℓ is horizontal. Moreover, we assume that p_1,…,p_n is the sequence of points of P in increasing order of their x-coordinates. We refer to a set of nonoverlapping disks centered at points of P as a feasible solution. We refer to the disks in a feasible solution S that are centered at p_1,…, p_n as D_1, …, D_n, respectively. Also, we denote the radius of D_i by r_i; it might be that r_i=0. For a feasible solution S we define α(S)=∑ r_i^2. Since the total area of the disks in S is π·α(S), hereafter, we refer to α(S) as the total area of disks in S. We call D_i a full disk if it has p_i-1 or p_i+1 on its boundary, a zero disk if its radius is zero, and a partial disk otherwise. For two points p_i and p_j, we denote the Euclidean distance between p_i and p_j by p_ip_j.

We briefly review the O(n^2)-time algorithm of Acharyya  <cit.>. First, compute a set 𝒟 of disks centered at points of P, which is the superset of every optimal solution. For every disk D∈𝒟, that is centered at a point p∈ P, define a weighted interval I whose length is 2r, where r is the radius of D, and whose center is p. Set the weight of I to be r^2. Let ℐ be the set of these intervals. The disks corresponding to the intervals in a maximum weight independent set of the intervals in ℐ forms an optimal solution to Problem 1. By construction, these disks are nonoverlapping, centered at p_1,…, p_n, and maximize the total area. Since the maximum weight independent set of m intervals that are given in sorted order of their left endpoints can be computed in O(m) time <cit.>, the time complexity of the above algorithm is essentially dominated by the size of 𝒟. Acharyya  <cit.> showed how to compute such a set 𝒟 of size Θ(n^2) and order the corresponding intervals in O(n^2) time. Therefore, the total running time of their algorithm is O(n^2). 

We show how to improve the running time to O(n). In fact we show how to find a set 𝒟 of size Θ(n) and order the corresponding intervals in O(n) time, provided that the points of P are given in sorted order.  



 §.§ Computation of 𝒟

In this section we show how to compute a set 𝒟 with a linear number of disks such that every disk in an optimal solution for Problem 1 belongs to 𝒟.

Our set 𝒟 is the union of three sets F, D, and D of disks that are computed as follows. The set F contains 2n disks representing the full disks and zero disks that are centered at points of P. We compute D by traversing the points of P from left to right as follows; the computation of D is symmetric. For each point p_i with i∈{2,…,n-1} we define its signature s(p_i) as 

    s(p_i) =
    
    +            if  p_i-1p_i⩽p_ip_i+1
    
    -       if  p_i-1p_i> p_ip_i+1.

Set s(p_1)=- and s(p_n)=+.
We refer to the sequence 𝒮=s(p_1),…,s(p_n) as the signature sequence of P. Let Δ be the multiset that contains all contiguous subsequences s(p_i),…,s(p_j) of 𝒮, with i<j, such that s(p_i)=s(p_j)=-, and s(p_k)=+ for all i< k< j; if j=i+1, then there is no k. For example, if 𝒮=-++-+++—+–++, then Δ={-++-, -+++-,–, –, -+-, –}. Observe that for every sequence s(p_i),…,s(p_j) in Δ we have that 

    p_ip_i+1⩽p_i+1p_i+2⩽p_i+2p_i+3⩽…⩽p_j-1p_j,  and  p_j-1p_j>p_jp_j+1.


Every plus sign in 𝒮 belongs to at most one sequence in Δ, and every minus sign in 𝒮 belongs to at most two sequences in Δ. Therefore, the size of Δ (the total length of its sequences) is at most 2n. For each sequence s(p_i),…,s(p_j) in Δ we add some disks to D as follows. Consider the full disk D_j at p_j. Iterate on k=j-1,j-2,…, i. In each iteration, consider the disk D_k that is centered at p_k and touches D_k+1. If D_k does not contain p_k-1 and its area is not larger than the area of D_k+1, then add D_k to D and proceed to the next iteration, otherwise, terminate the iteration. See Figure <ref>. This finishes the computation of D. Notice that D contains at most n-1 disks. The computation of D is symmetric; it is done in a similar way by traversing the points from right to left (all the + signatures become - and vice versa).



The number of disks in 𝒟= F∪D∪D is at most 4n-2. The signature sequence 𝒮 can be computed in linear time. Having 𝒮, we can compute the multiset Δ, the disks in D as well as the corresponding intervals, as in <cit.> and described before, in sorted order of their left endpoints in total O(n) time. Then the sorted intervals corresponding to circles in 𝒟 can be computed in linear-time by merging the sorted intervals that correspond to sets F, D, and D. It remains to show that 𝒟 contains an optimal solution for Problem 1. To that end, we first prove two lemmas about the structural properties of an optimal solution.


	
	Every feasible solution S for Problem 1 can be converted to a feasible solution S' where D_1 and D_n are full disks and α(S')⩾α(S).



	Recall that n⩾ 3. We prove this lemma for D_1; the proof for D_n is similar. Since S is a feasible solution, we have that r_1 + r_2 ⩽p_1p_2. Let S' be a solution that is obtained from S by making D_1 a full disk and D_2 a zero disk. Since we do not increase the radius of D_2, it does not overlap D_3, and thus, S' is a feasible solution. In S', the radius of D_1 is p_1p_2, and we have that r_1^2+r_2^2⩽ (r_1+r_2)^2⩽p_1p_2^2. This implies that α(S')⩾α(S).





	
	If D_i, with 1<i<n, is a partial disk in an optimal solution, then r_i<max(r_i-1,r_i+1).


	The proof is by contradiction; let S be such an optimal solution for which r_i⩾max(r_i-1, r_i+1). First assume that D_i touches at most one of D_i-1 and D_i+1. By slightly enlarging D_i and shrinking its touching neighbor we can increase the total area of S. Without loss of generality suppose that D_i touches D_i-1. Since r_i⩾ r_i-1, 
    (r_i+ϵ)^2+(r_i-1-ϵ)^2=r_i^2+r_i-1^2+2(r_iϵ-r_i-1ϵ+ϵ^2)>r_i^2+r_i-1^2>0,
 for any ϵ>0. This contradicts optimality of S. Now, assume that D_i touches both D_i-1 and D_i+1, and that r_i-1⩽ r_i+1. See Figure <ref>. We obtain a solution S' from S by enlarging D_i as much as possible, and simultaneously shrinking both D_i-1 and D_i+1. This makes D_i-1 a zero disk, D_i a full disk, D_i+1 a zero or a partial disk, and does not change the other disks. The difference between the total areas of S' and S is 
	
    ((r_i+r_i-1)^2 + (r_i+1-r_i-1)^2) -(r_i-1^2+r_i^2+r_i+1^2)=r_i-1^2+2r_i-1(r_i-r_i+1)>0;

	this inequality is valid since r_i⩾ r_i+1⩾ r_i-1>0.
	This contradicts the optimality of S.






	The set 𝒟 contains an optimal solution for Problem 1.



	It suffices to show that every disk D_k, which is centered at p_k, in an optimal solution S={D_1,…,D_n} belongs to 𝒟. By Lemma <ref>, we may assume that both D_1 and D_n are full disks. If D_k is a full disk or a zero disk, then it belongs to F. Assume that D_k is a partial disk. Since S is optimal, D_k touches at least one of D_k-1 and D_k+1, because otherwise we could enlarge D_k. 
	
	First assume that D_k touches exactly one disk, say D_k+1. We are going to show that D_k belongs to D (If D_k touches only D_k-1, by a similar reasoning we can show that D_k belongs to D). Notice that r_k<r_k+1, because otherwise we could enlarge D_k and shrink D_k+1 simultaneously to increase α(S), which contradicts the optimality of S. Since D_k is partial and touches D_k+1, we have that D_k+1 is either full or partial. If D_k+1 is full, then it has p_k+2 on its boundary, and thus s(p_k+1)=-. By our definition of Δ, for some i<k+1, the sequence s(p_i),…, s(p_k+1) belongs to Δ. Then by our construction of D both D_k+1 and D_k belong to D, where k+1 plays the role of j. Assume that D_k+1 is partial. Then D_k+2 touches D_k+1, because otherwise we could enlarge D_k+1 and shrink D_k simultaneously to increase α(S). Recall that r_k<r_k+1. Lemma <ref> implies that r_k+1<r_k+2. This implies that p_kp_k+1<p_k+1p_k+, and thus s(p_k+1)=+. Since D_k+1 is partial and touches D_k+2, we have that D_k+2 is either full or partial. If D_k+2 is full, then it has p_k+3 on its boundary, and thus s(p_k+2)=-. By a similar reasoning as for D_k+1 based on the definition of Δ and D, we get that D_k+2, D_k+1, and D_k are in D. If D_k+2 is partial, then it touches D_k+3 and again by Lemma <ref> we have r_k+2<r_k+3 and consequently s(p_k+2)=+. By repeating this process, we stop at some point p_j, with j⩽ n-2, for which D_j is a full disk, r_j-1<r_j, and s(p_j)=-; notice that such a j exists because D_n is a full disk and consequently D_n-1 is a zero disk. To this end we have that s(p_k)∈{+,-}, s(p_j)=-, and s(p_k+1),…, s(p_j-1) is a plus sequence. Thus, s(p_k),…,s(p_j) is a subsequence of some sequence s(p_i),…,s(p_j) in Δ. Our construction of D implies that all disks D_k, …, D_j belong to D. 
	
	
	Now assume that D_k touches both D_k-1 and D_k+1. By Lemma <ref> we have that D_k is strictly smaller than the largest of these disks, say D_k+1. By a similar reasoning as in the previous case we get that D_k∈D. 




§ PROBLEM 2: CLIENT-SERVER COVERAGE WITH MINIMUM RADII



In this section we study Problem 2: Let P={p_1,…,p_n} be a set of n points on a straight-line ℓ that is partitioned into two sets, namely clients and servers. We want to assign to every server in P a radius such that the disks with these radii cover all clients and the sum of their radii is as small as possible. Bilò  <cit.> showed that this problem can be solved in polynomial time. Lev-Tov and Peleg <cit.> showed how to obtain such an assignment in O(n^3) time. Alt  <cit.> presented an O(n log n)-time 2-approximation algorithm for this problem. We show how to solve this problem optimally in O(n^2) time. 


	Given a total of n collinear clients and servers, in O(n^2) time, we can find a set of disks centered at servers that cover all clients and where the sum of the radii of the disks is minimum.


Without loss of generality assume that ℓ is horizontal, and that p_1,…,p_n is the sequence of points of P in increasing order of their x-coordinates. We refer to a disk with radius zero as a zero disk, to a set of disks centered at servers and covering all clients as a feasible solution, and to the sum of the radii of the disks in a feasible solution as its cost. We denote the radius of a disk D by r(D), and denote by D(p,q) a disk that is centered at the point p with the point q on its boundary.

We describe a top-down dynamic programming algorithm that maintains a table T with n entries T(1),…, T(n). Each table entry T(k) represents the cost of an optimal solution for the subproblem that consists of points p_1,…,p_k. The optimal cost of the original problem will be stored in T(n); the optimal solution itself can be recovered from T. In the rest of this section we show how to solve a subproblem p_1,…,p_k. In fact, we show how to compute T(k) recursively by a top-down dynamic programming algorithm. 
To that end, we first describe our three base cases:

	
  * There is no client. In this case T(k)=0.
	
  * There are some clients but no server. In this case T(k)=+∞.
	
  * There are some clients and exactly one server, say s. In this case T(k) is the radius of the smallest disk that is centered at s and covers all the clients.
	

Assume that the subproblem p_1,…, p_k has at least one client and at least two servers. We are going to derive a recursion for T(k).


	
	Every disk in any optimal solution has a client on its boundary. 



	
	No disk contains the center of some other non-zero disk in an optimal solution. 



	Our proof is by contradiction. Let D_i and D_j be two disks in an optimal solution such that D_i contains the center of D_j. Let p_i and p_j be the centers of D_i and D_j, respectively, and r_i and r_j be the radii of D_i and D_j, respectively. See Figure <ref>(a). Since D_i contains p_j, we have r_i>p_ip_j. Let D'_i be the disk of radius p_ip_j+r_j that is centered at p_i. Notice that D'_i covers all the clients that are covered by D_i∪ D_j. By replacing D_i and D_j with D'_i we obtain a feasible solution whose cost is smaller than the optimal cost, because p_ip_j+r_j< r_i+r_j. This contradicts the optimality of the initial solution.  




Let c be the rightmost client in p_1,…, p_k. For a disk D that covers c, let ψ(D)∈{1,…,k} be the smallest index for which the point p_ψ(D) is in the interior or on the boundary of D, i.e., ψ(D) is the index of the leftmost point of p_1,…,p_k that is in D. See Figure <ref>(b). 

We claim that only one disk in an optimal solution can cover c, because, if two disks cover c then if their centers lie on the same side of c, we get a contradiction to Lemma <ref>, and if their centers lie on different sides of c, then by removing the disk whose center is to the right of c we obtain a feasible solution with smaller cost. 
Let S^* be an optimal solution (with minimum sum of the radii) that has a maximum number of non-zero disks. 
Let D^* be the disk in S^* that covers c. All other clients in p_ψ(D^*),…,p_k are also covered by D^*, and thus, they do not need to be covered by any other disk. As a consequence of Lemma <ref>, the servers that are in D^* and the servers that lie to the right of D^* cannot be used to cover any clients in p_1,…, p_ψ(D^*)-1. Therefore, if we have D^*, then the problem reduces to a smaller instance that consists of the points to the left of D^*, i.e., p_1,…, p_ψ(D^*)-1. See Figure <ref>(b). Thus, the cost of the optimal solution for the subproblem p_1,…, p_k can be computed as
T(k)=T(ψ(D^*)-1) + r(D^*). 

In the rest of this section we compute a set 𝒟_k of O(k) disks each of them covering c. Then we claim that D^* belongs to 𝒟_k. Having 𝒟_k, we can compute T(k) by the following recursion:

    T(k)=min{T(ψ(D)-1) + r(D): D∈𝒟_k}.
 

Now we show how to compute 𝒟_k. Recall from Observation <ref> that every disk in the optimal solution (including D^*) contains a client on its boundary. Using this observation, we compute 𝒟_k in two phases. In the first phase, for every server s we add the disk D(s,c) to 𝒟_k.
In the second phase, for every client c', with c' ≠ c, we add a disk D(s',c') to 𝒟_k, where s' is the first server to the right side of the midpoint of segment cc'. Since for every server and for every client (except for c) we add one disk to 𝒟_k, this set has at most k-1 disks. The disks that we add in phase one can be computed in O(k) time by sweeping the servers from right to left. The disks that we add in phase two can also be computed in O(k) time by sweeping the clients from right to left, using this property that the server s' associated with the next client c' is on or to the left side of the server associated with the current client. Hence, the set 𝒟_k, and consequently the entry T(k), can be computed in O(k) time. Therefore, our dynamic programming algorithm computes all entries of T in O(n^2) time.

One final issue we need to address is the correctness of our algorithm, which is to show that D^* belongs to 𝒟_k. Let s^* be the server that is the center of D^* and let c^* be the client on the boundary of D^* (such a client exists by Observation <ref>). Recall that D^* covers the rightmost client c. If c^*=c, then D^* has been added to 𝒟_k in the phase one.  Assume that c^*≠ c. In this case c^* is the left intersection point of the
boundary of D^* with ℓ because c^* is to the left side of c. Let m be the mid point of the line segment c^*c, and let s be the first server to the right of m. The server s^* cannot be to the left side of m because otherwise D^* could not cover c. Also, s^* cannot be to the right side of s because otherwise the disk D(s, c^*), which is smaller than D^*, covers the same set of clients as D^* does, in particular it covers c^* and c. Therefore, we have s^*=s, and thus D^*=D(s,c^*), which has been added to 𝒟_k in phase two. This finishes the proof of correctness of our algorithm. 





§ PROBLEM 3: POINT-INTERVAL COVERAGE WITH MINIMUM AREA


Let I=[a,b] be an interval on the x-axis in the plane. We say that a set of disks covers I if I is a subset of the union of the disks in this set. Let P={p_1,…,p_n} be a set of n points on I, that are ordered from left to right, and such that p_1=a and p_n=b. A point-interval coverage for the pair (P,I) is a set S={D_1,…,D_n} of n disks that cover I such that for every i∈{1,…,n} the disk D_i contains the point p_i, i.e., p_i is in the interior or on the boundary of D_i. See Figure <ref>. The point-interval coverage problem is to find such a set of disks with minimum total area. In this section we show how to solve this problem in O(n^2) time. 






	Given n points on an interval, in O(n^2) time, we can find a set of disks covering
	the entire interval such that every disk contains at least one point and where the total area of the disks is minimum.


If we drop the condition that D_i should contain p_i, then the problem can be solved in linear time by using Observation <ref> (which is stated below). 
First we prove some lemmas about the structural properties of an optimal point-interval coverage. We say that a disk is anchored at a point p if it has p on its boundary.
We say that two intersecting disks touch each other if their intersection is exactly one point, and we say that they overlap otherwise.








	
	There is no pair of overlapping disks in any optimal solution for the point-interval coverage problem. 



	Our proof is by contradiction. Consider two overlapping disks D_i and D_j, with i<j, in an optimal solution. Since D_i contains p_i and D_j contains p_j, there exists a point c on the line segment p_ip_j that is in D_i∩ D_j. Let c_i and c_j be the leftmost and the rightmost points of the interval that is covered by D_i∪ D_j; see Figure <ref>(a). Let D'_i and D'_j be the disks with diameters c_ic and cc_j, respectively. The areas of D'_i and D'_j are smaller than the areas of D_i and D_j, respectively. Moreover, D'_i contains p_i, D'_j contains p_j, and D'_i∪ D'_j covers the same interval [c_i,c_j] as D_i∪ D_j does. Therefore, by replacing D_i and D_j with D'_i and D'_j we obtain a solution whose total area is smaller than the optimal area, which is a contradiction.




	
	In any optimal solution, if the intersection point of D_i and D_i+1 does not belong to P, then D_i and D_i+1 have equal radius. 


	Let c be the intersection point of D_i and D_i+1. Let c_i be the left intersection point of the boundary of D_i with the x-axis, and let c_i+1 be the right intersection point of the boundary of D_i+1 with the x-axis; see Figure <ref>(b). We proceed by contradiction, and assume, without loss of generality, that D_i+1 is smaller than D_i. We shrink D_i (while anchored at c_i) and enlarge D_i+1 (while anchored at c_i+1) simultaneously by a small value. This gives a valid solution whose total area is smaller than the optimal area, because our gain in the area of D_i+1 is smaller than our loss from the area of D_i. This contradicts the optimality of our initial solution.


The following lemma and observation play important roles in our algorithm for the point-interval coverage problem, which we describe later.


	
	Let R>0 be a real number, and r_1,r_2,…,r_k be a sequence of positive real numbers such that 
	∑_i=1^k r_i = R. Then 
	
    ∑_i=1^k r_i^2 ≥∑_i=1^k (R/k)^2 = R^2/k ,
 
	i.e., the sum on the left-hand side of (<ref>) is minimum if all 
	r_i are equal to R/k. 
 

	If f is a convex function, then—by Jensen’s inequality—we have 
	
    f ( ∑_i=1^k r_i/k) ⩽∑_i=1^k f(r_i)/k .
  
	Since the function f(x) = x^2 is convex, 
	it follows that 
	
    ( R/k)^2 = f ( R/k)
    	= f ( ∑_i=1^k r_i/k)⩽∑_i=1^k r_i^2/k,

	which, in turn, implies Inequality (<ref>).
 

The minimum sum of the radii of a set of disks that cover I=[a,b] is |ab|/2. The following observation is implied by Lemma <ref>, by setting R=|ab|/2 and k=n. 


	
	The minimum total area of n disks covering I is obtained by a sequence of n disks of equal radius such that every two consecutive disks touch each other; see Figure <ref>.
  



We refer to the covering of I that is introduced in Observation <ref> as the unit-disk covering of I with n disks. Such a covering is called valid if it is a point-interval coverage for (P,I). 



 §.§ A Dynamic-Programming Algorithm


In this subsection we present an O(n^3)-time dynamic-programming algorithm for the point-interval coverage problem. In Subsection <ref> we show how to improve the running time to O(n^2).

First, we review some properties of an optimal solution for the point-interval coverage problem that enable us to present a top-down dynamic programming algorithm.
Let C^*=D_1,…,D_n be the sequence of n disks in an optimal solution for this problem. Recall that as a consequence of Lemma <ref>, the intersection of every two consecutive disks in C^* is a point. If there is no k∈{1,…, n-1} for which the intersection point of D_k and D_k+1 belongs to P, then Lemma <ref> implies that all disks in C^* have equal radius, and thus, C^* is a valid unit-disk covering. Assume that for some k∈{1,…, n-1} the intersection point of D_k and D_k+1 is a point p∈ P. Notice that either p=p_k or p=p_k+1. In either case, C^* is the union of the optimal solutions for two smaller problem-instances (P_1,I_1) and (P_2,I_2) where I_1=[a,p], I_2=[p,b], P_1={p_1,…,p_k} and P_2={p_k+1,…,p_n}.




We define a subproblem (P_ij,I_ij) and represent it by four indices (i,j,i',j') where 1⩽ i<j⩽ n and i',j'∈{0,1}. The indices i and j indicate that I_ij =[p_i,p_j]. The set P_ij contains the points of P that are on I_ij provided that p_i belongs to P_ij if and only if i'=1 and p_j belongs to P_ij if and only if j'=1. For example, if i'=1 and j'=0, then P_ij={p_i,p_i+1,…, p_j-1}. We define T(i,j,i',j') to be the cost (total area) of an optimal solution for subproblem (i,j,i',j'). The optimal cost of the original problem will be stored in T(1,n,1,1). We compute T(i,j,i',j') as follows. If the unit-disk covering is a valid solution for (i,j,i',j'), then by Observation <ref> it is optimal, and thus we assign its total area to T(i,j,i',j'). Otherwise, as we discussed earlier, there is a point p_k of P with k∈{i+1,…, j-1} that is the intersection point of two consecutive disks in the optimal solution. This splits the problem into two smaller subproblems, one to the left of p_k and one to the right of p_k. The point p_k is assigned either to the left subproblem or to the right subproblem. See Figure <ref> for an instance in which the unit-disk covering is not valid, and p_k is assigned to the right subproblem. In the optimal solution, p_k is assigned to the one that minimizes the total area, which is 

    T(i,j,i',j')=min{T(i,k,i',1)+T(k,j,0,j'), T(i,k,i',0)+T(k,j,1,j')}.

Since we do not know the value of k, we try all possible values and pick the one that minimizes T(i,j,i',j').

There are three base cases for the above recursion. (1) No point of P is assigned to the current subproblem: we assign +∞ to T(·), which implies this solution is not valid. (2) Exactly one point of P is assigned to the current subproblem: we cover [p_i,p_j] with one disk of diameter |p_ip_j| and assign its area to T(·). (3) More than one point of P is assigned to the current subproblem and the unit-disk covering is valid: we assign the total area of this unit-disk covering to T(·).

The total number of subproblems is at most 2· 2·n  2 = O(n^2), because i and j take n  2 different values, and each of i' and j' takes two different values. 
The time to solve each subproblem (i,j,i',j') is proportional to the time for checking the validity of the unit-disk covering for this subproblem plus the iteration of k from i+1 to j-1; these can be done in total time O(j-i). Thus, the running time of our dynamic programming algorithm is O(n^3). 

In the next section we present a more involved dynamic-programming algorithm that improves the running time to O(n^2). Essentially, our algorithm verifies the validity of the unit-disk coverings for all subproblems p_i,…,p_j in O(n^2) time.




 §.§ Improving the running time


We describe a top-down dynamic programming algorithm that maintains a table T with 2n entries T(j,j') where j∈{1,…, n} and j'∈{0,1}. Each entry T(j, j') represents the cost of an optimal solution for the subproblem that consists of interval I_j=[p_1,p_j] and a point set P_j. 
If j' = 1, then P_j = I_j ∩ P, whereas, if j' = 0, then P_j = I_j ∩ P ∖{ p_j }. 
The optimal cost of the original problem will be stored in T(n, 1); the optimal solution itself can be recovered from T. In the rest of this section we show how to solve subproblem (j,j'). If the unit-disk covering is a valid solution for (j,j'), then we assign its total area to T(j,j'). Otherwise, there must be some point p_k∈ P with k∈{2,…, j-1} that is the intersection point of two consecutive disks in the optimal solution. Let i be the largest such k. This choice of i implies that the interval [p_i,p_j] is covered by unit disks, and thus, we only need to solve the subproblem to the left of p_i optimally for two cases where i'=0 and i'=1. Let U(i,j,i'j') denote the cost of a unit-disk covering for the problem instance (i,j,i',j') (that is defined in the previous section). Then


    T(j,j')=min{T(i,1)+U(i,j,0,j'), T(i,0)+U(i,j,1,j')}.


Since we do not know the value of i, we try all possible values and pick the one
that minimizes T(j,j'). 

The total number of subproblems is 2n, and the time to solve each subproblem (j,j') is proportional to the total time for the iterations of i from 2 to j-1 plus the time for computing the unit-disk covering for (i,j,i',j') and checking its validity. Let u(j) denote the time for computing and checking validity of unit-disk coverings for all i. Then the time to compute T(j,j') is O(j)+u(j). Therefore, the running time of our algorithm, i.e. the time to compute T(n,1), is 
    ∑_j=1^nO(j)+u(j)=O(n^2)+∑_j=1^nu(j)=O(n^2)+∑_j=1^n∑_i=2^j-1u(i,j,i',j'),

where u(i,j,i',j') denotes the time of computing the unit-disk covering for (i,j,i',j') and checking its validity. In the rest of this section we will show how to do this, for all (i,j,i',j'), in O(n^2) time. This implies that the total running time of our algorithm is O(n^2).



Take any i∈{1,…, n-1}. We show how to check the validity of the unit-disk covering for (i,j,i',j'), where j iterates from i+1 to n. We are going to show how to do this in O(n-i) total time, for all values of j. This  will imply that we can check the validity of the unit-disk coverings for all i and j in O(n^2) time. We describe the procedure for the case when i'=1 and j'=1; the other three cases can be handled similarly. Recall that I_ij=[p_i,p_j] is the interval and P_ij={p_i,…,p_j} is the point set that are associated with (i,j,i',j'). Notice that the length of I_ij is |p_ip_j|, and the number of points in P_ij is n_ij=j-i+1.
Then the diameter of each disk in the unit-disk covering of (i,j,1,1) is d_ij=|p_ip_j|/n_ij.
In order to have a valid unit-disk covering for (i,j,1,1), the following conditions are necessary and sufficient (see Figure <ref>)


    |p_ip_i+1|  ⩽ d_ij
     d_ij⩽      |p_ip_i+2|  ⩽ 2· d_ij
     2· d_ij⩽      |p_ip_i+3|  ⩽ 3· d_ij
     3· d_ij⩽      |p_ip_i+4|  ⩽ 4· d_ij
           ⋮
      (n_ij-1)· d_ij⩽       |p_ip_j|   ⩽ n_ij· d_ij.

The above inequalities are equivalent to the following two inequalities

    d_ij⩾   max{|p_ip_i+1|,|p_ip_i+2|/2,|p_ip_i+3|/3,…, |p_ip_j|/n_ij},
    d_ij⩽   min{|p_ip_i+2|,|p_ip_i+3|/2,|p_ip_i+4|/3,…, |p_ip_j|/n_ij-1}.
 

Let M(i,j) denote the maximum value in Inequality (<ref>), and let m(i,j) denote the minimum value in Inequality (<ref>). To check the validity of the unit-disk covering for (i,j,1,1), it suffices to compare d_ij with these two values. Recall that i is fixed and j iterates from i+1 to n. Now we show how to check the validity of the unit-disk covering for subproblem (i,j+1,1,1), in  O(1)  time. In this subproblem, the diameter of the unit disks is d_i(j+1) and the number of points is n_i(j+1)=n_ij+1; these values can be computed in  O(1)  time. In order to have a valid unit-disk covering for (i,j+1,1,1), the following two inequalities are necessary and sufficient

    d_i(j+1)⩾   max{|p_ip_i+1|,|p_ip_i+2|/2,|p_ip_i+3|/3,…, |p_ip_j|/n_ij,|p_ip_j+1|/n_ij+1},
     d_i(j+1)⩽   min{|p_ip_i+2|,|p_ip_i+3|/2,|p_ip_i+4|/3,…, |p_ip_j|/n_ij-1, |p_ip_j+1|/n_ij}.


Thus, we can compute 

    M(i,j+1)=max{M(i,j), |p_ip_j+1|/n_ij+1},    and     m(i,j+1)=min{m(i,j), |p_ip_j+1|/n_ij},


in  O(1)  time. Then the unit-disk covering is valid for (i,j+1,1,1) if and only if 
m(i,j+1)⩽ d_i(j+1)⩽ M(i,j+1); this can be verified in  O(1)  time. Thus, by keeping M(i,j) and m(i,j) from the previous iteration, we can check the validity of the unit-disk covering for the current iteration, in  O(1)  time. Therefore, we can check the validity of (i,j,1,1) for all j∈{i+1,…,n} in O(n-i) total time. This finishes the proof.




§ CONCLUSION: AN OPEN PROBLEM

We considered three optimization problems on collinear points in the plane. Here we present a related open problem: given a set of collinear points, we want to assign to each point a disk, centered at that point, such that the underlying disk graph is connected and the sum of the areas of the disks is minimized. The disk graph has input points as its vertices, and has an edge between two points if their assigned disks intersect. It is not known whether or not this problem is NP-hard. In any dimension d⩾ 2 this problem is NP-hard if an upper bound on the radii of disks is given to us <cit.>.




abbrv

