0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ There can in general be an infinity of such squares, so what ? $\endgroup$
    – user65203
    Commented May 3, 2017 at 10:51
  • $\begingroup$ I just need to find one such square. $\endgroup$
    – user442931
    Commented May 3, 2017 at 10:55

2 Answers 2

Reset to default
0
$\begingroup$

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.

enter image description here

$\endgroup$
1
  • $\begingroup$ Thank you very much! My problem was that I was using a line instead of slab for sweeping and was only able to check one dimension at a time. Thanks again! $\endgroup$
    – user442931
    Commented May 3, 2017 at 12:16
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.