How to find independent points in a unit square in O(n log n)?

Question

Consider a unit square containing n 2D points. We say that two points p and q are independent in a square, if the Euclidean distance between them is greater than 1. A unit square can contain at most 3 mutually independent points. I would like to find those 3 mutually independent points in the given unit square in O(n log n). Is it possible? Please help me.

Can this problem be solved in O(n^2) without using any spatial data structures such as Quadtree, kd-tree, etc?

Answer 1

Use a spatial data structure such as a Quadtree to store your points. Each node in the quadtree has a bounding box and a set of 4 child nodes, and a list of points (empty except for the leaf nodes). The points are stored in the leaf nodes.

The point quadtree is an adaptation of a binary tree used to represent two-dimensional point data. It shares the features of all quadtrees but is a true tree as the center of a subdivision is always on a point. The tree shape depends on the order in which data is processed. It is often very efficient in comparing two-dimensional, ordered data points, usually operating in O(log n) time.

For each point, maintain a set of all points that are independent of that point.

Insert all your points into the quadtree, then iterate through the points and use the quadtree to find the points that are independent of each:

main()
{
     for each point p
         insert p into quadtree
         set p's set to empty

     for each point p
         findIndependentPoints(p, root node of quadtree)
}

findIndependentPoints(Point p, QuadTreeNode n)
{
     Point f = farthest corner of bounding box of n
     if distance between f and p < 1
         return  // none of the points in this node or
                 // its children are independent of p

     for each point q in n
         if distance between p and q > 1
             find intersection r of q's set and p's set
             if r is non-empty then
                 p, q, r are the 3 points -> ***SOLVED***
             add p to q's set of independent points
             add q to p's set of independent points

     for each subnode m of n (up 4 of them)
         findIndependentPoints(p, m)
}

You could speed up this:

find intersection r of q's set and p's set

by storing each set as a quadtree. Then you could find the intersection by searching in q's quadtree for a point independent of p using the same early-out technique:

// find intersection r of q's set and p's set:
//     r = findMututallyIndependentPoint(p, q's quadtree root)

Point findMututallyIndependentPoint(Point p, QuadTreeNode n)
{
     Point f = farthest corner of bounding box of n
     if distance between f and p < 1
         return  // none of the points in this node or
                 // its children are independent of p

     for each point r in n
         if distance between p and r > 1
             return r

     for each subnode m of n (up 4 of them)
         findMututallyIndependentPoint(p, m)
}

An alternative to using Quadtrees is using K-d trees, which produces more balanced trees where each leaf node is a similar depth from the root. The algorithm for finding independent points in that case would be the same, except that there would only be up to 2 and not 4 child nodes for each node in the data structure, and the bounding boxes at each level would be of variable size.

Answer 2

You might want to try this out.

Pick the top left point (Y) with coordinate (0,1). Calculate distance from each point from the List to point Y.
Sort the result in increasing order into SortedPointList (L)
If the first point (A) and the last point (B) in list L are independent:
    Foreach point P in list L:
        if P is independent to both A and B:
             Return A, B, P
Pick the top right point (X) with coordinate (1,1). Calculate distance from each point from the List to point X.
Sort the result in increasing order into SortedPointList (S)
If the first point (C) and the last point (D) in list L are independent:
    Foreach point O in list S:
        if P is independent to both C and D:
             Return C, D, O
Return null

Answer 3

This is a wrong solution. Kept it just for comments. If one finds another solution based on smallest enclosing circle, please put a link as a comment.

---

1. Solve the Smallest-circle problem.

2. If diameter of a circle <= 1, return null.

3. If the circle is determined by 3 points, check which are "mutually independent". If there are only two of them, try to find the third by iteration.

4. If the circle is determined by 2 points, they are "mutually independent". Try to find the third one by iteration.

Smallest-sircle problem can be solved in O(N), thus the whole problem complexity is also O(N).