Last ned (Gratis)

Abstrakt

In this paper we first prove that for any set points P in the plane, the
closest neighbor b to any point p in P is a proper triangle edge bp in D(P),
the Delaunay triangulation of P. We also generalize this result and prove
that the j’th (second, third, ..) closest neighbors b_j to p are also edges
pb_j in D(P) if they satisfy simple tests on distances from a point. Even
though we can find many of the edges in D(P) in this way by looking
at close neighbors, we give a three point example showing that not all
edges in D(P) will be found. For a random dataset we give results from
test runs and a model that show that our method finds on the average 4
edges per point in D(P). Also, we prove that the Delaunay edges found
in this way form a connected graph. We use these results to outline two
new parallel, and potentially faster algorithms for finding D(P). We then
report results from parallelizing one of these algorithms on a multicore
CPU (MPU), which resulted in a significant speedup; and on a graphics
card, a NVIDA GPU, where we experienced a speeddown. We explain
this by discussing the NVIDA SIMT programming model, how it differs
from the well-known SIMD model, and why a speeddown is obtained
instead of a speedup. Finally, we comment on the k’th closest neighbors
problem.

Referanser

[1] B. Delaunay, Sur la sphère vide, Izvestia Akademia Nauk SSSR, VII Seria,
Otdelenie Matematicheskii i Estestvennyka Nauk, vol. 7, 1934, p.793–800.



[2] Mourad Khayati and Jalel Akaichi, Incremental approach for Continuous
k-Nearest Neighbours queries on road, Iternational Journal of Intelligent
Information and Database Systems, Volume 2, Number 2, Pages: 204 - 221 ,
2008


[3] Arne Maus, Delaunay Triangulation and the Convex Hull of N Points in Expected
Linear Time, 1984, BIT, vol.24, p.151–163


[4] Dyken and Floater, Preferred Directions for Resolving the Non-uniqueness
of Delaunay Triangulations, CGTA: Computational Geometry: Theory and
Applications, vol.34, n. 2, p.96–101, 2006


[5] de Berg, Mark; Otfried Cheong, Marc van Kreveld, Mark Overmars (2008).
Computational Geometry: Algorithms and Applications. Springer-Verlag. ISBN
978-3-540-77973-5., http://www.cs.uu.nl/geobook/interpolation.pdf.
[6] Wu, LiXin(2008), Integral ear elimination and virtual point-based updating algorithms
for constrained Delaunay TIN. Science in China Series E Technological
Sciences 51,Pages 135-144 Issue Volume 51, Supplement 1 / April, 2008


[7] Edelsbrunner and Shah, Incremental Topological Flipping Works for Regular
Triangulations, ALGRTHMICA: Algorithmica, vol.15, 1996


[8] Øyvind Hjelle and Morten Dæhlen, Triangulations and Applications, Springer,
2006, Mathematics and Visualization, ISBN:978-3-540-33260-2


[9] Kieran F. Mulchrone, Application of Delaunay triangulation to the nearest
neighbour method of strain analysis Journal of Structural Geology, Volume 25,
Issue 5, Pages 689-702, May 2003,


[10] Arne Maus and Stein Gjessing, A Model for the Effect of Caching on
Algorithmic Efficiency in Radix based Sorting, The Second International
Conference on Software Engineering Advances, ICSEA 25. France, 2007


[11] Leonidas J. Guibas, Donald E. Knuth and Micha Sharir Randomized incremental
construction of Delaunay and Voronoi diagrams
Journal Algorithmica Publisher Springer New York ISSN 0178-4617 (Print) 1432-
0541 (Online) Pages 381-413 Issue Volume 7, Numbers 1-6, June, 1992


[12] Gabriel, K.R., and R.R. Sokal A new statistical approach to geographic
variation analysis. Systematic Zoology 18:259-278. 1969


[13] Wikipedia: Delaunay triangulation
http : //en.wikipedia.org/wiki/Delaunay_triangulation


[14] Wikipedia: Gabliel Graph
http : //en.wikipedia.org/wiki/Gabriel_graph


[15] Wikipedia: Polygon mesh
http : //en.wikipedia.org/wiki/P olygon_mesh


[16] Jon Moen Drange, Parallell Delaunay-triangulering i Java og CUDA. Master
Thesis (in Norwegian), Dept. of Informatics, Univ. Of Oslo, May 2010


[17] NVIDIA CUDA C Programming Guide Version 3.2, chapter 4.1, 4.2
http : //www.nvidia.com