1
$\begingroup$

Given a set of 'n' points, I need to construct a circle enclosing the points(might not be the smallest enclosing circle) given that minimum of 2 points lie on the circle. I want to find the result in order of 'n' time complexity.

What I tried: I tried by first finding the maximum and minimum x-coordinate and finding the distance between them and then repeating the same for y-coordinate. Then I found out the maximum distance out of the two(between x_min and x_max and between y_min and y_max). For the pair for which I got the maximum distance, I found the euclidean distance and took that as the diameter, and constructed the circle around it. For eg. if I found the maximum distance between x_min and x_max, I calculated the euclidean distance between (x_min,y1) and (x_min,y2) and considered it as the diameter.

But that seems to not work !!

$\endgroup$
6
  • $\begingroup$ A search for smallest circle containing a set of points finds this linear time algorithm: en.wikipedia.org/wiki/Smallest-circle_problem $\endgroup$ – Ethan Bolker Nov 12 '20 at 18:36
  • $\begingroup$ Is there some reason you are trying to delete the question part of your post? Describing what you tried is not useful without the explanation of what you are trying to do. Please do not deface your post. $\endgroup$ – Morgan Rodgers Nov 13 '20 at 7:26
  • $\begingroup$ Why did you vandalize my answer ? $\endgroup$ – Yves Daoust Nov 13 '20 at 7:41
  • $\begingroup$ I am about to give this question as an assignment to my students, so I wanted to delete the answer or else they will copy it from here. So I request you to please delete the answer. It will be really helpful. Sorry if I offended you. @YvesDaoust $\endgroup$ – Anonymoustez Nov 13 '20 at 8:09
  • $\begingroup$ Your request is triply shocking. You had to say it upfront. $\endgroup$ – Yves Daoust Nov 13 '20 at 8:11
3
$\begingroup$
  1. find the leftmost point in $O(n)$ operations (this is a point of the convex hull),

  2. find the leftmost point "around the first" in $O(n)$ operations (this is the next point on the hull),

  3. compute the radii of all circles by these two points and the remaining ones, in $O(n)$ operations. Keep the circle with the largest radius and you are done.

(The first two steps correspond to the start of a "Jarvis walk" https://en.wikipedia.org/wiki/Gift_wrapping_algorithm.)

enter image description here

$\endgroup$

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.