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).