A Compact Parallel Algorithm for Spherical Delaunay Triangulations
详细信息 查看全文
- 关键词：Spherical delaunay triangulation ; Parallel computing ; Computational geometry ; Interpolation
- 刊名：Lecture Notes in Computer Science
- 出版年：2016
- 出版时间：2016
- 年：2016
- 卷：9574
- 期：1
- 页码：355-364
- 全文大小：334 KB
- 参考文献：1.Bourke, P.: Efficient triangulation algorithm suitable for terrain modelling or an algorithm for interpolating irregularly-spaced data with applications in terrain modelling. In: Pan Pacific Computer Conference, Beijing, China (1989)
2.Bowyer, A.: Computing Dirichlet tessellations. Comput. J. 24(2), 162–166 (1981)MathSciNet CrossRef
3.Burnikel, C., Funke, S., Seel, M.: Exact geometric computation using cascading. IJCGA 11(3), 245–266 (2001)MathSciNet MATH
4.Carfora, M.F.: Interpolation on spherical geodesic grids: a comparative study. J. Comput. Appl. Math. 210(1–2), 99–105 (2007)MathSciNet CrossRef MATH
5.de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Heidelberg (2008)CrossRef MATH
6.Fasshauer, G.E., Schumaker, L.L.: Scattered data fitting on the sphere. In: Fasshauerand, G.E. (ed.) Mathematical Methods for Curves and Surfaces II, pp. 117–166. Vanderbilt University Press, Nashville (1998)
7.Jacobsen, D.W., Gunzburger, M., Ringler, T., Burkardt, J., Peterson, J.: Parallel algorithms for planar and spherical Delaunay construction with an application to centroidal Voronoi tessellations. Geosci. Model Dev. 6(4), 1353–1365 (2013)CrossRef
8.Ju, L., Ringler, T., Gunzburger, M.: Voronoi tessellations and their application to climate and global modeling. In: Lauritzen, P., Jablonowski, C., Taylor, M., Nair, R. (eds.) Numerical Techniques for Global Atmospheric Models. Lecture Notes in Computational Science and Engineering, vol. 80, pp. 313–342. Springer, Heidelberg (2011)CrossRef
9.Lawson, C.L.: \(C^1\) surface interpolation for scattered data on a sphere. Rocky Mt. J. Math. 14(1), 177–202 (1984)MathSciNet CrossRef MATH
10.Rakhmanov, E.A., Saff, E., Zhou, Y.: Minimal discrete energy on the sphere. Math. Res. Lett 1(6), 647–662 (1994)MathSciNet CrossRef MATH
11.Renka, R.J.: Interpolation of data on the surface of a sphere. ACM Trans. Math. Softw. 10(4), 417–436 (1984)MathSciNet CrossRef MATH
12.Renka, R.J.: Algorithm 772: STRIPACK: Delaunay triangulation and voronoi diagram on the surface of a sphere. ACM Trans. Math. Softw. 23(3), 416–434 (1997)MathSciNet CrossRef MATH
13.Shewchuk, J.R.: Lecture notes on Delaunay mesh generation. Department of Electrical Engineering and Computer Sciences, University of California at Berkeley (2012)
14.Watson, D.F.: Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. Comput. J. 24(2), 167–172 (1981)MathSciNet CrossRef
15.Zängl, G., Reinert, D., Rípodas, P., Baldauf, M.: The ICON (ICOsahedral Non-hydrostatic) modelling framework of DWD and MPI-M: description of the non-hydrostatic dynamical core. Q. J. R. Meteorol. Soc. 141(687), 563–579 (2015)CrossRef - 作者单位：Florian Prill (19)
Günther Zängl (19)
19. Deutscher Wetterdienst, Offenbach, Germany - 丛书名：Parallel Processing and Applied Mathematics
- ISBN：978-3-319-32152-3
- 刊物类别：Computer Science
- 刊物主题：Artificial Intelligence and Robotics
Computer Communication Networks
Software Engineering
Data Encryption
Database Management
Computation by Abstract Devices
Algorithm Analysis and Problem Complexity - 出版者：Springer Berlin / Heidelberg
- ISSN：1611-3349
文摘
We present a data-parallel algorithm for the construction of Delaunay triangulations on the sphere. Our method combines a variant of the classical Bowyer-Watson point insertion algorithm [2, 14] with the recently published parallelization technique by Jacobsen et al. [7]. It resolves a breakdown situation of the latter approach and is suitable for practical implementation due to its compact formulation. Some complementary aspects are discussed such as the parallel workload, floating-point arithmetics and an application to interpolation of scattered data.