Блог пользователя HekpoMaH

Автор HekpoMaH, 11 лет назад, По-английски

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

  • Проголосовать: нравится
  • -10
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
11 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

2D-tree