Quote:Original post by ApochPiQ
Voronoi diagrams are highly accurate but extremely inefficient in space - the figure O(n^3) sticks in my mind but I don't know for sure if that's correct off the top of my head. In practical terms, this means that a Voronoi-based solution will cost a ridiculous amount of memory for large numbers of points.

Are you certain? Seems to me that Euler's relationship would only yield a linear number of triangles in a triangulation, and thus a linear number of edges. So, it would only be a question of storing a linear-space search tree for the Delaunay triangulation, find the containing triangle in log-time, and then test the three vertices for proximity...

My mistake - Voronoi diagrams are O(n^2) in 3-space. This is still a highly expensive growth curve for any significant number of sample points. However, the query for the m closest points (not necessarily closest points of approach, mind) among a set of n points should average O(m log n) time, which is quite efficient, but not necessarily more efficient than the use of a balanced kd-tree. Notably, a kd-tree can easily be stored on O(n) space and queried in O(m + log n) time.

(See specifically Aurenhammer 1991, "Voronoi diagrams - a survey of a fundamental geometric data structure" and related findings and continued work by Jensen et. al., especially the use of kd-trees for similar calculations, as collected in Jensen 2001, "Realistic Image Synthesis Using Photon Mapping".)

Quote:Original post by ApochPiQ
(See specifically Aurenhammer 1991, "Voronoi diagrams - a survey of a fundamental geometric data structure" and related findings and continued work by Jensen et. al., especially the use of kd-trees for similar calculations, as collected in Jensen 2001, "Realistic Image Synthesis Using Photon Mapping".)

I've mentioned this on gamedev in the past, but it's worth a repeat. The code in Jensen's book for finding nearest neighbors in a k-d tree is suboptimal; a better approach is to use the nearest neighbor search (on k-d trees) as described in one of the original reports on k-d trees:

Friedman, Jerome. Jon Bentley. Raphael Finkel. "An Algorithm for Finding Best Matches in Logarithmic Expected Time." ACM Transactions on Mathematical Software, vol. 3, no. 3, pp. 209-226, September 1977. See also: ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/75/482/CS-TR-75-482.pdf

It's the "ball within bounds" stuff that they talk about in that report. Unfortunately their description of the algorithm is rather densely explained. There are other papers on the net that explain it better, but I don't have a reference off the top of my head. I give a clear explanation in my book also (pp 320-321).

Interesting, thanks - I'll have to check it out.