Given n points on the x-axis, we give arbitrary radius for each point such that each constructed circle doesn't overlap another constructed circle from another point. Which means these circles do not intersect each other, but one point still can lie on another circle boundary. Find the total maximum area of these circles?
My basic idea is to set the radius of the first point to be 'r' (0 <= r <= x[2] - x[1]), then the next radius will be (x[2] - x[1] - r), etc. Then I figure out the function F(x) which means the result of the problem. Find the maximum of this function seems to be right but in this case, it's not:
Ex: array of points X = [0, 1, 3, 6, 10]
mySol: array of radii R = [1, 0, 2, 1, 3] => result = 15*PI
rightAns: R = [ 1, 0, 2, 0, 4] => result = 21*PI (which is the maximum total area)
Which is the best approach for this problem?
This is essentially a quadratic optimization problem. We have five unknown radii $r_1, r_2, r_3, r_4$ and $r_5$ and boundary conditions $0 \leq r_i$, $r_i + r_{i+1} \leq d_i$, where $d_i$ is the distance between the $i$-th and $(i+1)$-st point. We want to maximize $f(r_1,\dots,r_5) = \pi (r_1^2 + \dots + r_5^2) $. Dropping $\pi$, Mathematica code for doing this would be
NMaximize[r1^2+r2^2+r3^2+r4^2+r5^2, {r1>=0,r2>=0,r3>=0,r4>=0,r5>=0,r1+r2<=1,r2+r3<=2,r3+r4<=3,r4+r5<=4}, {r1,r2,r3,r4,r5}],which yields the correct solution
{21., {r1 -> 1., r2 -> 0., r3 -> 2., r4 -> 0., r5 -> 4.}}.We could also do this by hand, since the function to be maximized is convex, and the domain implied by the boundary conditions is polyhedral. This means the maximum is attained at a vertex, i.e. a point where at least five independent constraints are active (equality holds). These are finitely many cases, and (smartly) checking them all by pen and paper is feasible for small numbers.
Finally, note that the active constraints in the maximum are $x_1 + x_2 \leq 1$, $0 \leq x_2$, $x_2 + x_3 \leq 2$, $x_4+x_5 \leq 4$ and $0 \leq x_4$. Not all boundary conditions of the form $r_i + r_{i+1} \leq d_i$ are active, instead two of the non-negativity conditions are. This explains why the original strategy of setting $r_{i+1} = d_i - r_i$ did not work out.