I've encountered a problem in a 2d game I'm working on right now that seems super simple, but I can't seem to find an optimal solution for it. I want to have a box that's as large as possible, which contains a single point (let's assume the middle) but does not contain any other points. A drawing here

I need the solution to keep it a square, and while I don't need global optimality, I do need the edge to go right up to the points. Any thoughts? I haven't had much sleep..so maybe my brain just isn't working and it's actually a really easy problem...

And in case you're curious, here's the dev blog for the game.

Does the box need to be axis-aligned or oriented?

Yes, it needs to be axis-aligned. Not sure if oriented would be any easier...?

Get the farthest point relative to the center point on both x and y axis and resize the rectangle to those values?

I need the square to NOT contain any of the points (except for the center one, to avoid the trivial solution where you just put the square outside the point cloud).

I don't need the square to actually be centered about the central point. So it should be allowed to move around, as long as it still contains the central point.

Furthermore, unless I'm misunderstanding your suggestion, I don't see how that would work for my drawing here: http://www.makeitsha...om/drawing/8753 The minimum distance point from the red center would be the black point furthest to the right - it is closest to the center in the Y direction, and using that distance would make the square too small. I also assume you don't mean the Euclidian distance, as that would make the square too big. Am I misunderstanding?

EDIT: Hmm I think for the fixed-center case, you can split up the points into 4 regions delineated by the 2 diagonals of the square. So all points in the "top" and "bottom" regions, you consider their "grow distance" to be the Y distance to the center, and for the "left" and "right" region you consider it the X distance. Then, you can find the point with the minimum "grow distance" and use that as your half-width.

Still thinking about the movable case..perhaps applying this iteratively would work...

Thanks for taking the time to reply!

After some digging, it is similar although not quite this problem here: http://chaoxuprime.com/2011/02/an-open-problem-axis-aligned-rectangle-packing-density

Humm...I hope this doesn't end up being some NP-complete or high-order polynomial algorithm where I have to brute force it (ie. try placing edges at every point and enumerating..??)...

I can only think of a way to make centered square. Not sure how correct it'll be.

1. Loop through all points and find lowest distance between center point and other points;
2. Create centered square in such way that the closest point would be on the line;
3. Test whether you have any extra points inside (extra test), and make square smaller by penetration distance.