Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

shas19's blog

Closest point for all points in a plane
By shas19, history, 8 years ago, In English

Given N points I need to find Closest point among all the given points to all the given 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?

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shas19 (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Voronoi diagram? :D

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You can use Voronoi diagram to solve the problem. Nearest points are neighbour cells in it. But this solution considered to be true hell.

Another one solution is to choose some random set of directions and for all point try to find the answer among closest points in these directions.

Also, take a look: link

There also was problem on SPOJ or something like that, but I don't remember it :)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain randomized solution in more details ?

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    The randomized solution has been described in this post.

    As for the problem on SPOJ, I think it's FAILURE

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Another task: https://www.hackerrank.com/challenges/meeting-point

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Deleted.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My Russian isn't that great, but I believe this is an explanation for the closest pair of points, not the closest point to every point.

    → Reply