largest empty sphere or rectangle

Question

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

Answer 1

One possible heuristic solution is to restrict the large rectangle so that it's axis-aligned. In this case, a rectangle can be bounded by at most 2 * d points, where each point represents a bounding min or max to one or more dimensions. It can be then be determined if a point is inside that rectangle in only O(d).

A heuristic method to make use of this is to pick 2 points, and use those to form an initial bounding box, then randomly add points. If the point is inside the box, shrink or split the box. If the point is outside of the box, try to make the box bigger. A single pass should take O(d * N) if the box is shrunk instead of split.

The quality perhaps can be improved a bit by ensuring that no point is within the bounding box formed by the two points. It might be ideal to find all pairs of points such that no point is within the bounding box, as when converted to a graph, they should help with expanding the solution in a less random way. Dynamic programming likely leads to an algorithm that is better than O(d*N^3) perhaps O(d*N^2) or better.