3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What do the notations [0,1,3,6,10] and [1,0,2,0,4] mean as giving possible solutions? That is, from the notations, what circles are constructed? $\endgroup$ – coffeemath Jun 13 at 5:27
  • 1
    $\begingroup$ Like at x = 0, we have a circle with radius = 1, at x = 1 circle with radius = 0, at x = 3 circle with radius = 2.... so the total area is (1^2 + 0^2 + 2^2 + 0^2 + 4^2)*PI = 21PI $\endgroup$ – Scorpio13 Jun 13 at 6:21
  • $\begingroup$ I've proven the strategy for 2, 3, 4, 5 and 6 points. For 7 points and greater it's still a little bit difficult... $\endgroup$ – Alan Tsai Jun 13 at 13:37
  • $\begingroup$ What is your strategy? Maybe figure small case will help me resolve the general case $\endgroup$ – Scorpio13 Jun 13 at 14:31
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ is there a feasible algorithm that can be implemented by programming languages like C or python? $\endgroup$ – Alan Tsai Jun 13 at 20:49
  • $\begingroup$ @AlanTsai I'm sure there is, check out CVXOPT for a python package on convex optimization, for example (haven't used it myself, however). $\endgroup$ – Josef E. Greilhuber Jun 13 at 21:10
  • $\begingroup$ It’s actually hard. I don’t know about convex optimization yet :). This problem is from a programming contest, the number of points is actually 200,000 and the range of x is from 0 to 10^9, which is very large :P $\endgroup$ – Scorpio13 Jun 14 at 1:08
  • $\begingroup$ Could somebody give me some good resources to learn about convex optimization please :P $\endgroup$ – Scorpio13 Jun 14 at 1:10
  • $\begingroup$ Each $r_i$ must also be at most the min of two adjacent distances between that point and the two points to the left and right (except endpoints which have one such constraint). $\endgroup$ – coffeemath Jun 14 at 5:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.