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
  • $\begingroup$ This was likely in the context of a class on linear programming? Then you need to write the equations (what are the parameters, the constraints, the objective function) and massage them (variable substitution) so they become linear. $\endgroup$ – Marc Glisse Mar 30 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.