In N (~ 500) dimensions, I wish to find out the largest sphere or rectangle such that the sphere/rectangle does not contain already existing points. The entire set of points is bounded in an axis-aligned rectangular box (lower and upper bounds on the values).

Is there any known polynomial time algorithm/method/code that I can use to solve my problem?

The two well known algorithms: i) the largest empty rectangle within a rectangle (http://www.cs.princeton.edu/~chazelle/pubs/ComputLargestEmptyRectangle.pdf) and, ii) finding largest empty circle within location constraints (http://www.cs.dartmouth.edu/reports/TR86-130.pdf) do not work.

Although the complexity of above algorithms is N log N or N^2 log N, where N is the number of already existing points, the complexity is also a linear function of the number of vertices of the convex hull or the bounding polygon. A rectangle in 500 dimensions will have 2^500 corners which makes the above techniques infeasible.

Ideally, I am looking for a method (it does not have to be exact) that can determine the largest cirle/rectangle in polynomial time in N (number of points) and D (the dimension).

Thank you.

  • $\begingroup$ Did you try asking on Stackoverflow? I'd be very surprised if an exact algorithm exists, but maybe there exist approximate algorithm that can get you something close to the biggest sphere. $\endgroup$ – user7530 Jul 11 '13 at 15:09
  • $\begingroup$ I already asked the question on stackoverflow. stackoverflow.com/questions/17595477/… $\endgroup$ – Santosh Tiwari Jul 11 '13 at 15:36

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.