I'm working on a problem and wondering if anyone can point me in good direction or at some existing source code.
I have a rectangle that contains some points and I'm trying to find the largest empty rectangular area inside it that doesn't contain any of the points with its side parallel to the original rectangle (See below)
Can anyone help, I can't use a brute force approach of scanning the largest rectangle as its going to be 25000x25000 and contain up to 3000 random points.
I was thinking some sort of 2D space partitioning, but not really don't anything with that before.
I'm not worried about the memory needed for any suggested solution, I just need to be able to find the largest area as fast as possible.
Does anyone have any recommendations of where to start.