Come up with a method to find the smallest circle that covers two points with its center in x axis

179 views Asked by At

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. There is no time or space requirement.

Although this problem seems simple, but I think it's kinda tricky to solve. Could you give some help? Thanks!

1

There are 1 answers

1
DrKoch On BEST ANSWER

If both points should lie on the circumfence of the circle:

  • find midpoint of [p1, p2]: midpoint := ((a1+a2)/2, (b1+b2)/2))
  • find line perpendicular to [p1, p2] in midpoint
  • find intersection of this line with x axis
  • this intersection is the midpoint of your circle

Edit

If both points should be part of the "filled" circle:

Find the x values of both points: a1, b1

If the center (found above) is within [(a1,0), (b1,0)] then you have the smallest circle

if the center found above is < a1 then move it to (a1,0)

if the center is > b1 then move it to (b1,0)