Closest point for all points in a plane

Revision en1, by shas19, 2016-07-21 01:45:20

Given N points I need to find Closest point to all the points in plane in less than O(n^2).

The distance used is Euclidean distance.

I came to know that for any metric distance we can use kd-Tree to solve such problems. (I may be wrong)

I also came to know that for chebychev distance the problem can be solved using orthogonal range querying and manhattan distance problem can also be converted into chebychev distance problem.

Is there any way to solve Euclidean distance problem more easily with some other trick?

Tags computational geometry

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English shas19 2016-07-21 01:48:20 33
en1 English shas19 2016-07-21 01:45:20 571 Initial revision (published)