Author |
Topic: distance of points (Read 611 times) |
|
birbal
Full Member
Gender: 
Posts: 250
|
 |
distance of points
« on: Dec 24th, 2009, 9:34am » |
 Quote  Modify
|
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 ?
|
|
 IP Logged |
The only thing we have to fear is fear itself!
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: distance of points
« Reply #1 on: Jan 2nd, 2010, 11:12am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
abhijeet
Newbie
Gender:
Posts: 3
|
|
Re: distance of points
« Reply #2 on: Jan 7th, 2010, 1:17am » |
Quote Modify
|
You can also use KD Trees for this
en.wikipedia.org/wiki/Kd-tree
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: distance of points
« Reply #3 on: Jan 7th, 2010, 1:31am » |
Quote Modify
|
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 Jan 8th, 2010, 3:36am, 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/
|
| « Last Edit: Jan 9th, 2010, 5:45pm by Hippo » |
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: distance of points
« Reply #4 on: Jan 8th, 2010, 3:36am » |
Quote Modify
|
@hippo
can you please explain Voronoi Diagram and how to make it ?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
baba
Newbie
Gender:
Posts: 14
|
|
Re: distance of points
« Reply #5 on: Feb 7th, 2010, 11:31am » |
Quote Modify
|
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). 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print