Three-dimensional alpha shapes

DOI10.1145/174462.156635MaRDI QIDQ4296530zbMATH OpenOpenAlexWikidataFDO

Authors E. P. Mücke, Herbert Edelsbrunner

Publication date 19 June 1994

Published in ACM Transactions on Graphics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9410208

zbMATH Keywords

\(\alpha\)-shapescomputational graphicsDelaunay triangulationgeometric algorithmsrobust implementation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Frequently, data in scientific computing is in its abstract form a finite point set in space, and it is sometimes useful or required to compute what one might call the ``shape of the set. For that purpose, this paper introduces the formal notion of the family of $alpha$-shapes of a finite point set in $Rea{l}^3$. Each shape is a well-defined polytope, derived from the Delaunay triangulation of the point set, with a parameter $alphainReal$ controlling the desired level of detail. An algorithm is presented that constructs the entire family of shapes for a given set of size $n$ in time $O(n^2)$, worst case. A robust implementation of the algorithm is discussed and several applications in the area of scientific computing are mentioned.

Recommendations

• scientific article; zbMATH DE number 3854464
• scientific article; zbMATH DE number 1189236
• 3D kinetic alpha complexes and their implementation
• Efficient generation of simple polygons for characterizing the shape of a set of points in the plane
• Combinatorial Image Analysis

Cited in

(only showing first 100 items - show all)

• Quality mesh generation for molecular skin surfaces using restricted union of balls
• A topological sampling theorem for robust boundary reconstruction and image segmentation
• A sampling theory for compact sets in Euclidean space
• Fractional step like schemes for free surface problems with thermal coupling using the Lagrangian PFEM
• Improved boundary tracking in meshless simulations of free-surface flows
• Provably correct reconstruction of surfaces from sparse noisy samples
• Micro-genetic approach for surface meshing on a set of unorganized points
• Normalized implicit eigenvector least squares operators for noisy scattered data: Radial basis functions
• \(r\)-regular shape reconstruction from unorganized points
• On the definition and the construction of pockets in macromolecules
• Current trends in geometric modeling and selected computational applications
• Polyhedrization of an arbitrary 3D point set.
• Reconstruction of surfaces of revolution with partial sampling.
• Computational topology: Ambient isotopic approximation of 2-manifolds.
• Overview and recent advances in natural neighbour Galerkin methods
• Smooth surface reconstruction via natural neighbour interpolation of distance functions
• Denoising point sets via \(L_0\) minimization
• Using the medial axis to represent flow features for feature-aligned unstructured quad-dominant mesh generation
• An ALE-PFEM method for the numerical simulation of two-phase mixture flow
• Multiscale persistent functions for biomolecular structure characterization
• Statistics for data with geometric structure. Abstracts from the workshop held January 21--27, 2018
• Simulation of wave overtopping of maritime structures in a numerical wave flume
• The maximum opposite angulation for mesh construction
• Dynamic maintenance and visualization of molecular surfaces.
• The union of balls and its dual shape
• Incremental topological flipping works for regular triangulations
• Regularization of discrete contour by Willmore energy
• The least square particle finite element method for simulating large amplitude sloshing flows
• Zigzag persistence
• Surface reconstruction via cooperative evolutions
• A unified Lagrangian formulation for solid and fluid dynamics and its possibility for modelling submarine landslides and their consequences
• Modeling continuous grain crushing in granular media: a hybrid peridynamics and physics engine approach
• A fully partitioned Lagrangian framework for FSI problems characterized by free surfaces, large solid deformations and displacements, and strong added-mass effects
• Generation of segmental chips in metal cutting modeled with the PFEM
• Principal component analysis of persistent homology rank functions with case studies of spatial point patterns, sphere packing and colloids
• Continuation of point clouds via persistence diagrams
• Second-order consensus protocols based on transformed \(d\)-path Laplacians
• Holes and dependences in an ordered complex
• Representing implicit surfaces satisfying Lipschitz conditions by 4-dimensional point sets
• Local Delaunay-based high fidelity surface reconstruction from 3D point sets
• The neural particle method - an updated Lagrangian physics informed neural network for computational fluid dynamics
• Mathematical optimization problems for particle finite element analysis applied to 2D landslide modeling
• Persistent homology in \(\ell_\infty\) metric
• Level set and density estimation on manifolds
• Continuous and discrete radius functions on Voronoi tessellations and Delaunay mosaics
• Topological data analysis for the energy and stability of endohedral metallofullerenes
• A mixed u-p edge-based smoothed particle finite element formulation for viscous flow simulations
• Two-phase PFEM with stable nodal integration for large deformation hydromechanical coupled geotechnical problems
• Boundary estimation from point clouds: algorithms, guarantees and applications
• An enhanced semi-explicit particle finite element method for incompressible flows
• A Lagrangian nodal integration method for free-surface fluid flows
• A prediction method based on the voxel model and the finite cell method for cutting force-induced deformation in the five-axis milling process
• Modelling 3D metal cutting problems with the particle finite element method
• Parallel computation of alpha complexes for biomolecules
• Improving accuracy of the moving grid particle finite element method via a scheme based on Strang splitting
• The weighted mean curvature derivative of a space-filling diagram
• The weighted Gaussian curvature derivative of a space-filling diagram
• Implicit reconstructions of thin leaf surfaces from large, noisy point clouds
• Shape of an arbitrary finite point set in \(\mathbb{R}^2\)
• Quasi-molecular modeling of a single supercooled large droplet impact
• Twisty Takens: a geometric characterization of good observations on dense trajectories
• 3D regularized \(\mu(I)\)-rheology for granular flows simulation
• Order-k -hulls and -shapes
• Cohomological learning of periodic motion
• \(N\)-body gravitational and contact dynamics for asteroid aggregation
• Finite calculus formulations for finite element analysis of incompressible flows. Eulerian, ALE and Lagrangian approaches
• Fluid-structure interaction using the particle finite element method
• Three-dimensional simulation of aluminium extrusion by the \(\alpha\)-shape based natural element method
• To mesh or not to mesh. That is the question\(\dots \)
• On Poincaré cone property
• Blending isogeometric analysis and local \textit{maximum entropy} meshfree approximants
• Advances in stabilized finite element and particle methods for bulk forming processes
• Finding the homology of submanifolds with high confidence from random samples
• Smooth manifold reconstruction from noisy and non-uniform approximation with guarantees
• Recent advances in the meshless simulation of aluminium extrusion and other related forming processes
• Geometric modeling applications in rational drug design: a survey
• Geometric filtering of pairwise atomic interactions applied to the design of efficient statistical potentials
• A general framework for progressive point-sampled geometry
• A particle finite element method for analysis of industrial forming processes
• A particle finite element method for machining simulations
• On the employ of meshless methods in biomechanics
• Constructive implicit fitting
• Unified Lagrangian formulation for solid and fluid mechanics and FSI problems
• Unified Lagrangian formulation for elastic solids and incompressible fluids: application to fluid-structure interaction problems via the PFEM
• Advances in the particle finite element method for the analysis of fluid-multibody interaction and bed erosion in free surface flows
• Analyzing animal escape data with circular nonparametric multimodal regression
• Recovering the homology of immersed manifolds
• Atom simplification and quality T-mesh generation for multi-resolution biomolecular surfaces
• Testing uniformity for the case of a planar unknown support
• Multi-core CPU or GPU-accelerated multiscale modeling for biomolecular complexes
• Measuring shape with topology
• A new particle method for simulation of incompressible free surface flow problems
• The particle finite element method (PFEM) in thermo-mechanical problems
• A Lagrangian finite element approach for the analysis of fluid-structure interaction problems
• Scale selection for geometric fitting in noisy point clouds
• Point-cloud method for image-based biomechanical stress analysis
• From empirical data to inter-individual interactions: unveiling the rules of collective animal behavior
• Alpha, Betti and the megaparsec universe: on the topology of the cosmic web
• Level set and density estimation on manifolds
• scientific article; zbMATH DE number 3854464 (Why is no real title available?)

This page was built for publication: Three-dimensional alpha shapes

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