I have a question about the following problem and the two points need not be located on the circumference of such "smallest circle". I know this is a linear-programming problem but I just don't know how to solve it mathematically.

Give two planar points p1=(a1,b1) and p2=(a2,b2) and a line y=0, design an algorithm to find the smallest circle that covers both points such that its center (x*, 0) lies on y=0.

  • 1
    $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael May 23 '16 at 14:25
  • $\begingroup$ Are there any cases where both points are not on the boundary of the circle unless $(a_2-a_1)^2 + b_2^2 \lneq b_1^2$ (wlog $b_1 \leq b_2$), i.e. the lower point lies within the circle that is spanned by the upper one? $\endgroup$ – Martin Glauer May 23 '16 at 14:30

Don't solve it mathematically. Solve it by hand for a few cases first, and then have a go at making it mathematical. That way you will actually understand what you are doing.

The plane is divided up into points which are closer to $(a_1,b_1)$ than to $(a_2,b_2)$, points which are further away, and points which are equidistant. The $x$-axis is divided in the same way.

In the zone where points are closer to $(a_1,b_1)$, the radius of the circle (with a centre at such a point) is governed by the distance to the further point, $(a_2,b_2)$. So, in that part of the $x$-axis, you are trying to minimise the distance to $(a_2,b_2)$. That is a quadratic function of $x$ (or rather, its square is; but minimising the distance is the same as minimising the square).

In the zone where points are further from $(a_1,b_1)$, the radius of the circle is governed by the distance to $(a_1,b_1)$. So minimise that.

The zone (or, rather, the point on the $x$-axis) where the points are equidistant doesn't need special treatment because you can treat it as being a member of both the above zones at once.

So you already have an algorithm, more or less: find the minimum radius for the "closer to $(a_1,b_1)$" part of the $x$-axis, find the minimum radius for the "closer to $(a_2,b_2)$ part, and pick the minimum of the two minima.

But for real understanding, consider the possible geometries of the distance function in each of the two halves, and how the geometry of one half might relate to the geometry of the other half. Because nobody wants a solution to the question (it is known!) so the only benefit of doing the work is to gain understanding.


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.