Voronoi-Based Point-Placement for Three-Dimensional Delaunay-Refinement

Engwirda, Darren

Home/Archive/NASA NTRS

NASA NTRS · 20150023397

Voronoi-Based Point-Placement for Three-Dimensional Delaunay-Refinement

Engwirda, Darren

View original source ↗Export metadata ↓

Abstract

An extension of the restricted Delaunay-refinement algorithm for three-dimensional tetrahedral mesh generation is described, in which an off-centre type point-placement scheme is utilised. It is shown that the use of generalised Steiner points, positioned along edges in the associated Voronoi complex, typically leads to improvements in the overall size, quality and grading of the resulting tetrahedral meshes. The new algorithm can be viewed as a Frontal-Delaunay approach - a hybridisation of conventional Delaunay-refinement and advancing-front techniques, in which new vertices are positioned to satisfy both element size- and shapeconstraints. The new method is shown to inherit many of the best features of classical Delaunay-refinement and advancing-front type algorithms, combining good practical performance with theoretical robustness. Experimental comparisons show that

Explore related subjects

algorithms tetrahedrons grid generation (mathematics)

Keep this discovery

Explore connections, maps & timelines

BibTeX RIS

Engwirda, Darren. 2015-11-03. Voronoi-Based Point-Placement for Three-Dimensional Delaunay-Refinement. https://ntrs.nasa.gov/citations/20150023397

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related reports

DOE OSTI2025

SNoGloDe: A Structured Nonlinear Global Decomposition Solver

Large-scale optimization problems often require decomposition strategies and customized algorithms to achieve optimal solutions within a reasonable time. Building on the work of Cao and Zavala (2019) for solving nonlinear two-stage stochastic programs to global optimality, we implement and extend their approach. We generalize to optimization problems reformulated with a block-angular constraint structure (e.g., temporal decomposition). Our framework, written in Python using Pyomo, is highly customizable and enables parallel execution of the decomposition. SNoGloDe allows tailored branching strategies, lower bounding problems, and candidate generators to leverage problem-specific knowledge. To demonstrate effectiveness, we compare SNoGloDe’s performance with Gurobi on a temporally decomposed produced water case study.

algorithms↗

DOE OSTI2025

Extracting scattering amplitudes for arbitrary two-particle systems with one-particle left-hand cuts via lattice QCD

We derive a general formalism that relates the spectrum of two-particle systems in a finite volume to physical scattering amplitudes, taking into account the presence of any left-hand branch cuts due to single-particle exchanges. The method first relates the finite-volume spectrum to an infinite-volume short-range quantity, denoted ${\mathcal{M}}_0$, and then relates the latter to the physical scattering amplitudes via known integral equations. The derivation of both relations is performed using all-orders perturbation theory and is exact up to neglected exponentially suppressed volume dependence. The relations hold for arbitrary two-particle systems with any number of coupled channels, non-identical and non-degenerate particles, and any intrinsic spin.

algorithms↗

DOE OSTI2025

Sempervirens: A Fast Reconstruction Algorithm for Noisy and Incomplete Binary Matrix Representations of Trees

Applications such as reconstructing cell lineage trees (represented as phylogenetic trees) from single-cell sequencing data require reconstructing a {0,1}-matrix that has many errors and missing entries. We introduce Sempervirens, a very fast matrix reconstruction algorithm for noisy and incomplete matrix representations of phylogenetic trees. Sempervirens uses an iterative maximum-likelihood approach to determine the topology tree represented by the corrupted data. We show that Sempervirens is at least three orders of magnitude faster than other methods on thousand by thousand matrices, with the speed gap widening with larger matrices. We also show that Sempervirens matches state-of-the-art methods in reconstruction accuracy. The speed of Sempervirens enables it to be tractably applied to reconstructing much larger matrices than those that other methods can reconstruct. In addition to experimental results, we justify the algorithm with a mathematical treatment of its subprocedures.

algorithms↗