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 squared independent if the Euclidean distance between them is greater than 1. A unit square can contain no more than 3 mutually independent points. I would like to find these 3 mutually independent points in a given unit square in O (n log n). Is it possible? Please help me.

Is it possible to solve this problem in O (n ^ 2) without using any spatial data structures like Quadtree, kd-tree, etc.

Answer 1

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

Point quadrit is an adaptation of a binary tree used to represent two-dimensional point data. He shares the features of all quadrants, but is a true tree, since the center of the unit is always on the point. The shape of the tree depends on the processing order. This is often very effective when comparing two-dimensional ordered data points, usually working 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 quadrant, then iterate over the points and use the quadrant to find points that are independent of each:

main() { for each point p insert p into quadtree set p 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 set and p set if r is non-empty then p, q, r are the 3 points -> ***SOLVED*** add p to q set of independent points add q to p set of independent points for each subnode m of n (up 4 of them) findIndependentPoints(p, m) } 

You can speed it up:

 find intersection r of q set and p set 

saving each set as a quadrant. Then you can find the intersection by searching q quadtree for a point independent of p using the same technique:

 // find intersection r of q set and p set: // r = findMututallyIndependentPoint(p, q 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 to use Kd trees , which produces more balanced trees, where each leaf node is a similar depth from the root. The algorithm for finding independent points in this case will be the same, except that there will only be up to 2 in the data structure. not 4 child nodes for each node, but the bounding fields at each level will have a variable size.

Answer 2

You might want to try it.

 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 the wrong decision. Please do not go down. Saved it for comment only. If you find another solution based on the smallest vicious circle, put the link as a comment.

---

• Solve the Problem with the smallest circle .
• If circle diameter <= 1, return zero.

• If the circle is defined by three points, check which of them are "mutually independent." If there are only two, try finding the third one by iteration.

• If a circle is defined by two points, they are "mutually independent." Try to find the third iteration.

The Smallest-Circle problem can be solved in O (N), so the whole complexity of the problem is also O (N).