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

consider unit square containing n 2d points. 2 points p , q independent in square, if euclidean distance between them greater 1. unit square can contain @ 3 mutually independent points. find 3 mutually independent points in given unit square in o(n log n). possible? please me.

can problem solved in o(n^2) without using spatial data structures such quadtree, kd-tree, etc?

use spatial data structure such quadtree store points. each node in quadtree has bounding box , set of 4 child nodes, , list of points (empty except leaf nodes). points stored in leaf nodes.

the point quadtree adaptation of binary tree used represent two-dimensional point data. shares features of quadtrees true tree center of subdivision on point. tree shape depends on order in data processed. efficient in comparing two-dimensional, ordered data points, operating in o(log n) time.

for each point, maintain set of points independent of point.

insert points quadtree, iterate through points , use quadtree find points independent of each:

main() {      each point p          insert p quadtree          set p's set empty       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 , p < 1          return  // none of points in node or                  // children independent of p       each point q in n          if distance between p , q > 1              find intersection r of q's set , p's set              if r non-empty                  p, q, r 3 points -> ***solved***              add p q's set of independent points              add q p's set of independent points       each subnode m of n (up 4 of them)          findindependentpoints(p, m) } 

you speed this:

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

by storing each set quadtree. find intersection searching in q's quadtree point independent of p using same early-out technique:

// find intersection r of q's set , 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 , p < 1          return  // none of points in node or                  // children independent of p       each point r in n          if distance between p , r > 1              return r       each subnode m of n (up 4 of them)          findmututallyindependentpoint(p, m) } 

an alternative using quadtrees using k-d trees, produces more balanced trees each leaf node similar depth root. algorithm finding independent points in case same, except there 2 , not 4 child nodes each node in data structure, , bounding boxes @ each level of variable size.