given n points on $\mathbb{R^2}$ $\{(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)\}$

formulate a linear program to maximize the sum of the circumference of all circles so any two circles won't intersect (two tangent circles are allowed).

i successfully formulated the target function that i need to maximize $$\max \sum \limits_{i=1}^{n}2R_i\pi$$ where $R_i$ is the radius of circle $i$, but when i try to formulate the restrictions i get for any $1\le i \le n$ and any $1\le j\le n$ such that $j\not =i$ $$(x_i-x_j)^2+(y_i-y_j)^2 \ge (R_i+R_j)^2 $$

its not longer linear . so its not a proper linear program . i guess there must be some kind of clever trick or alternative formulation that i fail to think of.

this is a home-work question so i would prefer a hint or a solution to a similar problem instead of full solution to this problem .



You can actually just take the square root here:

$R_i+R_j \le \sqrt{(x_i−x_j)^2+(y_i−y_j)^2}$

  • $\begingroup$ i think that all the variables need to be linear to each other . like $a_1x_1 = a_2x_2 +/- a_3x_3 +/- \dots +/- a_kx_k$ this way we can always express any one of them in linear form. just by negating from the both sides the needed variables $\endgroup$ – Boris Morozov Jun 25 '14 at 13:24
  • $\begingroup$ The expression is linear in the $R_i$s which you are trying to optimize. The term on the RHS may look complicated, but in terms of radii it is just a constant like any other constant. You may as well call this $z_{ij}$ without losing any useful information. $\endgroup$ – Wonder Jun 25 '14 at 13:28
  • $\begingroup$ thx i think i understand $\endgroup$ – Boris Morozov Jun 25 '14 at 13:30


$d_{ij}= \sqrt{(x_i - x_j)^2 + (y_i-y_j)^2} \quad \forall i<j$

then just ask for

$ R_i+R_j \leq d_{ij} \quad \forall i<j$

and thus a linear program. You should force

$R_i\geq0 \quad \forall i$,

but since your maximizing is redundant.


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.