Nearest neighbor search with additional weight

Revision en4, by xagofes, 2019-02-24 01:00:07

There is a grid of size N * N. Each cell of the grid contains a magic positive integer. The distance between two cells is equal to the sum of the magic numbers in these cells and the Euclidean distance between these cells. Among all these cells, the R cells are painted red and the G cells are painted green. For each green cell, we need to find such a red one that there is no other red cell, the distance to which is less.

512 <= N <= 4096

1 <= R + G <= N * N

Is it possible to make it better than O(G * R)?

If there were no magic number in the cells, it would be Nearest neighbor search problem.

#### History

Revisions

Rev. Lang. By When Δ Comment
en4 xagofes 2019-02-24 01:00:07 2
en3 xagofes 2019-02-24 00:56:48 0 (published)
ru4 xagofes 2019-02-24 00:56:21 0 (опубликовано)
ru3 xagofes 2019-02-24 00:56:05 2 Мелкая правка: ' <= 4096\n1 <= R +' -> ' <= 4096\n\n1 <= R +'
en2 xagofes 2019-02-24 00:55:48 2 Tiny change: ' <= 4096\n1 <= R +' -> ' <= 4096\n\n1 <= R +'
en1 xagofes 2019-02-24 00:55:08 715 Initial revision for English translation (saved to drafts)
ru2 xagofes 2019-02-24 00:45:07 2 Мелкая правка: 'го соседа] https://en' -> 'го соседа](https://en'
ru1 xagofes 2019-02-24 00:44:31 734 Первая редакция (сохранено в черновиках)