Load-Balancing for Parallel Delaunay Triangulations

DOI10.1007/978-3-030-29400-7_12MaRDI QIDQ3297568zbMATH OpenOpenAlexFDO

Authors Daniel Funke, Peter Sanders, Vincent Winkler

Publication date 20 July 2020

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.07554, https://publikationen.bibliothek.kit.edu/1000117450

Mathematics Subject Classification ID

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

Abstract: Computing the Delaunay triangulation (DT) of a given point set in $mathbb{R}^D$ is one of the fundamental operations in computational geometry. Recently, Funke and Sanders (2017) presented 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.

Recommendations

• Parallel d-D Delaunay triangulations in shared and distributed memory
• Localizing the Delaunay triangulation and its parallel implementation
• PARALLEL DELAUNAY REFINEMENT: ALGORITHMS AND ANALYSES
• Distributed parallel Delaunay mesh generation
• scientific article; zbMATH DE number 1822225

Cites work

• Adaptive precision floating-point arithmetic and fast robust geometric predicates
• An Efficient Heuristic Procedure for Partitioning Graphs
• DeWall: a fast divide and conquer Delaunay triangulation algorithm in \(E^d\).
• Efficient Collision Detection of Complex Deformable Models using AABB Trees
• Efficient parallel random sampling-vectorized, cache-efficient, and online
• How Good is Recursive Bisection?
• Parallel d-D Delaunay triangulations in shared and distributed memory
• Parallel computational geometry
• Parallel geometric algorithms for multi-core computers
• Parallel mesh generation
• Simultaneous mesh generation and partitioning for Delaunay meshes
• THE DELAUNAY HIERARCHY

Cited in

(3)

• Localizing the Delaunay triangulation and its parallel implementation
• PARALLEL DELAUNAY REFINEMENT: ALGORITHMS AND ANALYSES
• Parallel d-D Delaunay triangulations in shared and distributed memory

Describes a project that uses

Uses Software

• CGAL
• DeWall
• Triangle

This page was built for publication: Load-Balancing for Parallel Delaunay Triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3297568)