Given a list of squares L, each embedded (non-overlapping) in an n x n grid, I would like to find the sidelength of the largest square (not in L) which contains an given position (i,j) and does not intersect any square in L.
Each square is represented by the position of its top-left corner and its sidelength, so it is very efficient to check whether two squares intersect.
How might I optimally find the value I describe above?
The algorithm I currently have essentially brute-force checks through every possible square containing (i,j) and keeps track of the maximal sidelength among those which intersect no square in L. I imagine this is nowhere close to optimal, although I've had trouble coming up with anything significantly faster.