HekpoMaH's blog

Voronoi Diagrams
By HekpoMaH, 11 years ago, In English

Here you are a task. Given set of N points in a plane. You have M queries: given a point P (x,y), which is the closest point of the given one.

I heard that could be done by Voronoi Diagrams. Is it true? Could you provide me some source about solving this task via using this kind of structure, because all I found on the was related to visualiaton?

P.S. Is there another structure that could be used for this task.

THANKS A LOT

  • Vote: I like it
  • -10
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I heard that could be done by Voronoi Diagrams. Is it true?

You've heard?

If you read wiki on Voronoi's diagram you should conclude that it is just direct solution for your task.

You can find links to algorithms here also.

Though much depends on your limits. Voronoi's diagram is just the most efficient way.

However, in certain cases you can split your space by rectangular grid and for each query P(x,y) simply find the point among the same cell where your query hits or one of its neighbors. This is popular approach in games, I believe.

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

"P.S. Is there another structure that could be used for this task."

2D-tree

→ Reply