Fast algorithm for testing if every rectangle built using any two points from a list contains a third point from that list

3
votes

The problem is as it follows:

Given N (N <= 100,000) points by their Cartesian coordinates, test if every rectangle (with an area > 0) built using any two of them contains at least another point from that list either inside the rectangle or on his margin.

I know the algorithm for O(N^2) time complexity. I want to find the solution for O(N * logN). Memory is not a problem.

When I say two points define a rectangle, I mean that those two points are in two of its opposite corners. The sides of the rectangles are parallel to the Cartesian axes.

Here are two examples:

N = 4

Points:

1 1

3 5

2 4

8 8

INCORRECT: (the rectangle (1, 1) - (2, 4) doesn't have any point inside of it or on its margin).

N = 3

Points:

10 9

13 9

10 8

CORRECT.

2
algorithmcomputational-geometry
A line-segment can be defined by 2 points, doesn't a rectangle (a plane) need at least 3 points? - Bruce Dean
@BruceDean But as you point out, there's no other way to define a rectangle using only two points, so it is kind of an obvious assumption; you may be confused by the fact that you can't define a plane in 3D space using only 2 points. The more important assumption, I think, is that the sides of the rectangles are parallel to the cartesian axes. - Kyle Strand
@Kyle: In theory, a rectangle could be defined from a half-diagonal: corner and centre. However, in that case, order is important. - rossum
Can you explain the last example? - Lasse V. Karlsen
@LasseV.Karlsen Note the "area > 0" requirement.... - Kyle Strand

2 Answers

2
votes

Sort the points in order of the max of their coordinate pairs, from lowest to highest (O(n*log(n))). Starting with the lower-left point (lowest max coordinate), if the next point in the ordering does not share either the original point's x-value or its y-value (e.g. (1,2) and (5,2) share a y-coordinate of 2, but (1,2) and (2, 1) have neither coordinate in common), the set of points fails the test. Otherwise, move to the next point. If you reach the final point in this way (O(n)), the set is valid. The algorithm overall is O(n*log(n)).

Explanation

Two points that share a coordinate value lie along a line parallel to one of the axes, so there is no rectangle drawn between them (since such a rectangle would have area=0).

For a given point p1, if the next "bigger" point in the ordering, p2, is directly vertical or horizontal from p1 (i.e. it shares a coordinate value), then all points to the upper-right of p2 form rectangles with p1 that include p2, so there are no rectangles in the set that have p1 as the lower-left corner and lack an internal point.

If, however, the next-bigger point is diagonal from p2, then the p1 <-> p2 rectangle has no points from the set inside it, so the set is invalid.

1
votes

For every point P = (a, b) in the set, search the nearest points of the form Y = (x, b) and X = (a, y) such that x > a and y > b.

Then, find if the rectangle defined by the two points X, Y contains any* internal point R besides P, X and Y. If that is the case, it's easy to see that the rectangle P, R does not contain any other point in the set.

If no point in the set exists matching the restrictions for X or Y, then you have to use (a, ∞) or (∞, b) respectively instead.

The computational cost of the algorithm is O(NlogN):

  • Looking for X or Y can be done using binary search [O(logN)] over a presorted list [O(NlogN)].

  • Looking for R can be done using some spatial tree structure as a quadtree or a k-d tree [O(logN)].

*) If X, Y contains more than one internal point, R should be selected as the nearest to P.

Update: the algorithm above works for rectangles defined by its botton-left and upper-right corners. In order to make it work also for rectangles defined by its botton-right and upper-left corners, a new point X' (such that it is the nearest one to P of the form X' = (a, y') where y' < b) and the corresponding rectangle defined by X', Y should also be considered for every point in the set.