to avoid decreasing precision error we can find delaunay triangulation of m points and for each n points we can first find which delaunay triangle it is in, compare these three points
and its adjcent triangle. at least one of the point with minmum distance in these three triangles,  if we find three point of one triangle if equal to minimum distance, continue to
find its adjcent triangles.

sorry for so many dumplicate post with so fucking network

Edited by author 21.10.2016 14:59

to  decreasing precision error we can find delaunay triangulation of m points and for each n points we can first find which delaunay triangle it is in, compare these three points
and its adjcent triangle. at least one of the point with minmum distance in these three triangles,  if we find three point of one triangle if equal to minimum distance, continue to
find its adjcent triangles.

to  decreasing precision error we can find delaunay triangulation of m points and for each n points we can first find which delaunay triangle it is in, compare these three points
and its adjcent triangle. at least one of the point with minmum distance in these three triangles,  if we find three point of one triangle if equal to minimum distance, continue to
find its adjcent triangles.

to  decreasing precision error we can find delaunay triangulation of m points and for each n points we can first find which delaunay triangle it is in, compare these three points
and its adjcent triangle. at least one of the point with minmum distance in these three triangles,  if we find three point of one triangle if equal to minimum distance, continue to
find its adjcent triangles.

I thought about Delanau triangulation. I have nD implementation of Quickhull algo, which can give me triangulation, when applied to projection onto paraboloid. Bit it is not too hard to imagine bad case for BFS on triangulation graph. E.g. well known concentric points. It is the same bad case as for quadtree.

Edited by author 10.11.2016 18:12

Does your last solution use this algorithm?

NO，  my AC sol directly find voronoi diagram but when Location the point, you mustn't find the intersection point of x==x0  instead you should find the nearest Thiessen polygons directly using Euclid distance to sort it..

in a word you should use original point as much as you can to inprove your accuracy

btw seems there is some clever k-d tree sol also get AC...

Edited by author 20.12.2017 21:58

What do you think, are top 3 solution implemented via Voronoi?

I implemented Fortune's (https://github.com/tomilov/sweepline), but I can't overcome precision errors in case of regular grids and concentric points, even if I use a little cheating: I modify input by rotation on some small angle. Some of points became a points-in-general-positions.

Then I use something like this (http://www.link.cs.cmu.edu/15859-f07/papers/point-location.pdf), but invented by myself - it is much simplier for Voronoi diagram.

I interested to talk with you (I will not bother you much), can you give any contact?

Edited by author 21.12.2017 19:51

you can contact me through 441766573@qq.com  my qq is always online...

You can remove the number and add me to your contacts =).