wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> distance of points
        
(Message started by: birbal on Dec 24^th, 2009, 9:34am)

Title: distance of points
Post by birbal on Dec 24^th, 2009, 9:34am

Given n points on a 2D coordinate system . What is the most efficient way of finding nearest point for each point? How can we find all the points at a distance k from a given point efficiently? Also does the method followed will depend on the density of points ?

Title: Re: distance of points
Post by inexorable on Jan 2^nd, 2010, 11:12am

Plane sweep algorithm can be used to find the nearest point to each point in O(nlogn).

For a given specific point you can do a plane sweep from X-K coordinate to X+K coordinate to find all points within K distance.

If many queries, for all points within k distance are expected. then preprocessing can be done by constructing n-ary tree with each node representing a square on plane with all points present in it.

Title: Re: distance of points
Post by abhijeet on Jan 7^th, 2010, 1:17am

You can also use KD Trees for this

en.wikipedia.org/wiki/Kd-tree

Title: Re: distance of points
Post by Hippo on Jan 7^th, 2010, 1:31am

I would construct Voronoi diagram/Delaunay triangulation at first (in O(n log n)). The triangulation has O(n) edges so leaving only minimal directed one going from a vertex neads an additional O(n) time.

on 01/08/10 at 03:36:01, birbal wrote:

@hippo
can you please explain Voronoi Diagram and how to make it ?

Google will ... line sweep algorithm.

one of the first hits ... http://www.diku.dk/hjemmesider/studerende/duff/Fortune/

Title: Re: distance of points
Post by birbal on Jan 8^th, 2010, 3:36am

@hippo
can you please explain Voronoi Diagram and how to make it ?

Title: Re: distance of points
Post by baba on Feb 7^th, 2010, 11:31am

Isn't this similar to the Top K selection from N given items. Can't we apply Selection Algorithm to get the k nearest point in O(n). :-/