Given set of points (in the plane), find in a linear time the smallest width annulus (annulus is the region between two concentric circles) that contains all the points.

Because of the time constraint we can't use any type sort/tree, also I've tried to think about using selection algorithm, but I can't think of a way to find the circles center point accordingly.

Can you think about any solution?

  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Feb 11 at 0:06
  • 2
    $\begingroup$ Can you credit the source where you originally encountered this problem? What makes you certain it can be done in linear time? $\endgroup$ – D.W. Feb 11 at 0:07
  • $\begingroup$ Where did you find this problem? There is no known linear time algorithm to do this. $\endgroup$ – Evil Feb 11 at 0:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.