Empty square 1x1 in a plane of $n$ points

Question

Let's say $P$ is a plane of $n$ points and $R$ axis-aligned minimum bounding rectangle. I need to find empty, axis-aligned square of size $1$ inside $R$ (if it exists), using sweep-line algorithm in $O(n \log n)$.

I had several ideas including: sorting points by x-coordinate and sweep through them, then adding them to a data structure (for example binary search tree) if the distance on x-axis between them was $\leq1$ and sorting them by y-coordinate, but I got stuck and haven't been able to figure out the solution.

Is there a data structure that would be useful in solving this problem?

Any advice would be very much appreciated.

Answer 1

For the sweep process, you can consider a slab one unit large at a time (as you said in your post). In a given progress state, you will update the slab by moving it to the next new point and discarding the old points trailing by more than one unit.

For a given position of the slab, you need to find a void which is one unit long (across the other coordinate). Entering a new point does not create opportunities to place a square. But when you discard a point, you can determine its distance to its two nearest neighbors and detect suitable voids.

Answer 2

In a different setting of the problem, you can replace all the given points by unit squares, and check for holes in the union of the squares.

The union of axis aligned rectangles is a classical problem.