×

Load-balancing for parallel Delaunay triangulations. (English) Zbl 1437.68187

Yahyapour, Ramin (ed.), Euro-Par 2019: parallel processing. 25th international conference on parallel and distributed computing, Göttingen, Germany, August 26–30, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11725, 156-169 (2019).
Summary: Computing the Delaunay triangulation (DT) of a given point set in \(\mathbb{R}^D\) is one of the fundamental operations in computational geometry. Recently, the first two authors presented [in: Proceedings of the 19th workshop on algorithm engineering and experiments, ALENEX ’17. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 207–217 (2017; Zbl 1430.68370)] a divide-and-conquer DT algorithm that merges two partial triangulations by re-triangulating a small subset of their vertices – the border vertices – and combining the three triangulations efficiently via parallel hash table lookups. The input point division should therefore yield roughly equal-sized partitions for good load-balancing and also result in a small number of border vertices for fast merging. In this paper, we present a novel divide-step based on partitioning the triangulation of a small sample of the input points. In experiments on synthetic and real-world data sets, we achieve nearly perfectly balanced partitions and small border triangulations. This almost cuts running time in half compared to non-data-sensitive division schemes on inputs exhibiting an exploitable underlying structure.
For the entire collection see [Zbl 1435.68044].

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W10 Parallel algorithms in computer science
68W15 Distributed algorithms

Citations:

Zbl 1430.68370

Software:

DeWall; Triangle; CGAL
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Aggarwal, A., Chazelle, B., Guibas, L.: Parallel computational geometry. Algorithmica 3(1), 293-327 (1988) · Zbl 0664.68041 · doi:10.1007/BF01762120
[2] Akhremtsev, Y., Sanders, P., Schulz, C.: High-quality shared-memory graph partitioning. In: Aldinucci, M., Padovani, L., Torquati, M. (eds.) Euro-Par 2018. LNCS, vol. 11014, pp. 659-671. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96983-1_47 · doi:10.1007/978-3-319-96983-1_47
[3] Batista, V.H., Millman, D.L., Pion, S., Singler, J.: Parallel geometric algorithms for multi-core computers. Comp. Geom. 43(8), 663-677 (2010) · Zbl 1344.68254 · doi:10.1016/j.comgeo.2010.04.008
[4] van den Bergen, G.: Efficient collision detection of complex deformable models using aabb trees. J. Graph. Tools 2(4), 1-13 (1997) · Zbl 0927.68100 · doi:10.1080/10867651.1997.10487480
[5] Chen, M.B.: The merge phase of parallel divide-and-conquer scheme for 3D Delaunay triangulation. In: International Symposium on Parallel and Distributed Processing with Applications (ISPA), pp. 224-230, IEEE (2010)
[6] Chrisochoides, N.: Parallel mesh generation. Numerical Solution of Partial Differential Equations on Parallel Computers. LNCS, vol. 51, pp. 237-264. Springer, Berlin (2006). https://doi.org/10.1007/3-540-31619-1_7 · Zbl 1097.65122 · doi:10.1007/3-540-31619-1_7
[7] Chrisochoides, N., Nave, D.: Simultaneous mesh generation and partitioning for Delaunay meshes. Math. Comput. Sim. 54(4), 321-339 (2000) · Zbl 0993.65029 · doi:10.1016/S0378-4754(00)00192-0
[8] Cignoni, P., Montani, C., Scopigno, R.: DeWall: a fast divide and conquer Delaunay triangulation algorithm in \(E^d\). CAD 30(5), 333-341 (1998) · Zbl 1035.68122
[9] Collaboration, G.: Gaia data release 2. summary of the contents and survey properties. arXiv (abs/1804.09365) (2018)
[10] Devillers, O.: The Delaunay hierarchy. Int. J. Found. Comput. Sci. 13(02), 163-180 (2002) · Zbl 1066.68138 · doi:10.1142/S0129054102001035
[11] Funke, D., Sanders, P.: Parallel \(d\)-d Delaunay triangulations in shared and distributed memory. In: ALENEX, pp. 207-217, SIAM (2017) · Zbl 1430.68370
[12] Funke, D., Sanders, P., Winkler, V.: Load-Balancing for Parallel Delaunay Triangulations. arXiv (abs/1902.07554) (2019)
[13] Hert, S., Seel, M.: dD convex hulls and delaunay triangulations. In: CGAL User and Reference Manual, CGAL Editorial Board, 4.7 edn. (2015)
[14] Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Techn. J. 49(2), 291-307 (1970) · Zbl 0333.05001 · doi:10.1002/j.1538-7305.1970.tb01770.x
[15] Kohout, J., Kolingerová, I., Žára, J.: Parallel Delaunay triangulation in E2 and E3 for computers with shared memory. Par. Comp. 31(5), 491-522 (2005) · doi:10.1016/j.parco.2005.02.010
[16] Larsson, T., Akenine-Möller, T., Lengyel, E.: On faster sphere-box overlap testing. J. Graph., GPU, Game Tools 12(1), 3-8 (2007) · doi:10.1080/2151237X.2007.10129232
[17] Lee, S., Park, C.I., Park, C.M.: An improved parallel algorithm for Delaunay triangulation on distributed memory parallel computers. Parallel Process. Lett. 11, 341-352 (2001) · doi:10.1142/S0129626401000634
[18] Sanders, P., Lamm, S., Hübschle-Schneider, L., Schrade, E., Dachsbacher, C.: Efficient parallel random sampling - vectorized, cache-efficient, and online. ACM Trans. Math. Softw. 44(3), 29:1-29:14 (2018) · Zbl 1484.65008 · doi:10.1145/3157734
[19] Sanders, P., Schulz, C.: Think locally, act globally: highly balanced graph partitioning. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 164-175. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38527-8_16 · doi:10.1007/978-3-642-38527-8_16
[20] Shewchuk, J.: Triangle: engineering a 2D quality mesh generator and Delaunay triangulator. Appl. Comp. Geom. Towards Geom. Eng. 1148, 203-222 (1996) · doi:10.1007/BFb0014497
[21] Shewchuk, J.: Adaptive precision floating-point arithmetic and fast robust geometric predicates. Disc. Comp. Geom. 18(3), 305-363 (1997) · Zbl 0892.68098 · doi:10.1007/PL00009321
[22] Simon, H.D., Teng, S.H.: How good is recursive bisection? J. Sci. Comput. 18(5), 1436-1445 (1997) · Zbl 0886.68104
[23] Su, P.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.