Three-dimensional alpha shapes

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 article introduces the formal notion of the family of &agr;-shapes of a finite point set in R3. Each shape is a well-defined polytope, derived from the Delaunay triangulation of the point set, with a parameter &agr; &egr; R 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 0(n2), worst case. A robust implementation of the algorithm is discussed, and several applications in the area of scientific computing are mentioned.

• Publication year

  1994

• Venue

  ACM Transactions on Graphics

• Publication date

  1994-01-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/174462.156635arXiv math/9410208
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Properties of Gabriel Graphs Relevant to Geographic Variation Research and the Clustering of Points in the Plane

  2010cited by this paper
• Marching cubes: a high resolution 3D surface construction algorithm

  1998cited by this paper
• Introduction to algorithms

  1996cited by this paper
• Closed Object Boundaries from Scattered Points

  1994cited by this paper
• Shapes and implementations in three-dimensional geometry

  1993cited by this paper
• Representing geometric structures ind dimensions: Topology and order

  1993cited by this paper
• Three-dimensional alpha shapes

  1992cited by this paper
• Incremental topological flipping works for regular triangulations

  1992cited by this paper
• Linear optimization queries

  1992cited by this paper
• Protein Folding

  1992cited by this paper
• Weighted alpha shapes

  1992cited by this paper
• Construction of three-dimensional Delaunay triangulations using local transformations

  1991cited by this paper
• The universe in a box : thermal effects in the standard cold dark matter scenario

  1990cited by this paper
• Exact Upper Bounds for the Number of Faces in d-Dimensional Voronoi Diagrams

  1990cited by this paper
• Regular Triangulations of Convex Polvtopes

  1990cited by this paper
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms

  1990cited by this paper
• Representing geometric structures in d dimensions: topology and order

  1989cited by this paper
• Higher-dimensional voronoi diagrams in linear expected time

  1989cited by this paper
• Three-dimensional triangulations from local transformations

  1989cited by this paper
• Volume rendering

  1988cited by this paper
• Protein folding

  1988cited by this paper
• Primitives for the manipulation of three-dimensional subdivisions

  1987cited by this paper
• Algorithms in Combinatorial Geometry

  1987cited by this paper
• Constructing higher-dimensional convex hulls at logarithmic cost per face

  1986cited by this paper
• Computational Geometry

  1985cited by this paper
• A Framework for Computational Morphology

  1985cited by this paper
• Geometric structures for three-dimensional shape representation

  1984cited by this paper
• AN INTRODUCTION TO CONVEX POLYTOPES (Graduate Texts in Mathematics, 90)

  1984cited by this paper
• Segmenting Dot Patterns by Voronoi Diagram Concavity

  1983cited by this paper
• On the shape of a set of points in the plane

  1983cited by this paper
• Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams

  1983cited by this paper
• Primitives for the manipulation of general subdivisions and the computation of Voronoi

  1983cited by this paper
• An Introduction to Convex Polytopes

  1982cited by this paper
• The relative neighbourhood graph of a finite planar set

  1980cited by this paper
• Software for C1 Surface Interpolation

  1977cited by this paper
• Graphs, surfaces, and homology

  1977cited by this paper
• Convex Polytopes and the Upper Bound Conjecture

  1971cited by this paper
• Some New Analytic and Graphic Approaches to Numerical Taxonomy, with an Example from the Dermanyssidae (ACARI)

  1967cited by this paper
• Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Premier mémoire. Sur quelques propriétés des formes quadratiques positives parfaites.

  1908cited by this paper
• Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs.

  year unknowncited by this paper

• Enhancing Scan-to-BIM for reinforced concrete bridges using point cloud completion techniques

  2026cites this paper
• A new meshfree method for accurate and efficient solutions to solid mechanics problems involving large deviatoric deformation, fracture, and fragmentation

  2026cites this paper
• FitTree: robust 3d tree mesh reconstruction from point clouds

  2026cites this paper
• A numerical framework for fibre orientation prediction in fibre-reinforced concrete tunnel linings

  2026cites this paper
• Novel distance-based masking and adaptive alpha-shape methods for CNN-ready reconstruction of arbitrary 2D CFD flow domains

  2026cites this paper
• Solvent‐Mediated Self‐Assembly and Hydrogen Bonding in Neutral Alginate: A Molecular Dynamics Study

  2026cites this paper
• Multiscale structural analysis of defective graphene in transmission electron microscopy images using persistent homology

  2026cites this paper
• Dynamic Evolution and Degradation of Silicon-Electrolyte Interfaces under Cycling via Chemical Potential-Controlled Molecular Dynamics.

  2026cites this paper
• Kombination multimodaler Sensordaten für eine verbesserte Nutzung von Schrott in der Stahlproduktion

  2026cites this paper
• TFRSUB: A terrain-feature retention and spatial uniformity balancing method for simplifying LiDAR ground point clouds

  2026cites this paper
• A novel three-dimensional canopy photosynthesis model for tea plant: integrating point cloud deep learning and ray tracing to optimize photosynthetic efficiency

  2026cites this paper
• Evaluating Airborne LiDAR Data-Derived Canopy Geometry for 3-D Radiative Transfer Simulations

  2026cites this paper
• Joint Orientation and Weight Optimization for Robust Watertight Surface Reconstruction via Dirichlet-Regularized Winding Fields

  2026cites this paper
• Continuum architecture dynamics of vesicle tethering in exocytosis.

  2026cites this paper
• Semantically Guided 3D Reconstruction and Body Weight Estimation Method for Dairy Cows

  2026influential citation
• Class-Partitioned VQ-VAE and Latent Flow Matching for Point Cloud Scene Generation

  2026cites this paper
• Precise volume assessment for gastrocnemius muscles based on 3D ultrasound imaging.

  2026cites this paper
• Multi-modal Data Driven Virtual Base Station Construction for Massive MIMO Beam Alignment

  2026cites this paper
• Evaluation of automatic geometry acquisition and point cloud registration methods for the repair of metallic components using Wire-Arc Additive Manufacturing

  2026cites this paper
• Dynamic LOD generation method for 3D geological models based on geological structural geometry features

  2026cites this paper
• Persistent homology via curvature-adaptive wing complexes

  2026cites this paper
• Delineating the Distribution Outline of Populus euphratica in the Mainstream Area of the Tarim River Using Multi-Source Thematic Classification Data

  2026cites this paper
• Selective Reinforcement Optimization for Composite Laminates

  2026cites this paper
• Automated Extraction of 3-D Windows From MVS Point Clouds by Comprehensive Fusion of Multitype Features

  2026cites this paper
• Reconstructing coniferous tree crown shape from incomplete point clouds using deep learning

  2026cites this paper
• Robust Interplanetary Trajectory Design for Missed Thrust Events using Reachable Sets with Solar Electric Propulsion and Solar Sail

  2026cites this paper
• A space–time particle-position-based finite element formulation for free-surface flows

  2026cites this paper
• Characterisations and molecular docking of cathepsin B cysteine proteinase a novel drug target for parasitic nematode Trichinella spiralis

  2026cites this paper
• An automatic seam extraction method based on improved DLP structured light vision inrobotic welding

  2026cites this paper
• Grapevine Canopy Volume Estimation from UAV Photogrammetric Point Clouds at Different Flight Heights

  2026cites this paper
• Rheological control of cementitious composites incorporating ceramic wastes for 3D printing applications

  2026cites this paper
• Towards a human-like observer: applying deep learning in an extended Wigner’s friend experiment

  2025cites this paper
• SHREC 2025: Protein Surface Shape Retrieval including Electrostatic potential

  2025cites this paper
• DeepSES: Learning solvent-excluded surfaces via neural signed distance fields

  2025cites this paper
• Chromatin binding regulates phase behavior and morphology of condensates formed by prion-like domains.

  2025cites this paper
• A mesh-based Graph Neural Network approach for surrogate modeling of Lagrangian free surface fluid flows

  2025cites this paper
• Shock-induced thermal stability of compacted cyclotrimethylene trinitramine explosive: Effect of densification and particle size

  2025cites this paper
• Computational Modeling of Bridging Vein Rupture and Acute Subdural Hematoma Growth

  2025cites this paper
• Crank-rocker optical fiber mode scrambler prototype for the GMT-Consortium Large Earth Finder (G-CLEF)

  2025cites this paper
• Classification of Histopathology Slides with Persistence Homology Convolutions

  2025cites this paper
• CaNetiCs - An Open-Source Toolbox for Standardized Dimensionality Reduction of Neuronal Calcium Activity

  2025cites this paper
• Proposing a framework for body mass prediction with point clouds: A study applied in typical swine pen environments

  2025cites this paper
• Design Space Exploration via Gaussian Process Regression and Alpha Shape Visualization

  2025cites this paper
• Estimating Biomass in Eucalyptus globulus and Pinus pinaster Forests Using UAV-Based LiDAR in Central and Northern Portugal

  2025cites this paper
• Component Contour-Based Viewpoint Planning for UAV Scene Coverage

  2025cites this paper
• Geometric deep learning adapted to prediction of liver resection zone

  2025cites this paper
• Multi-physics two-layer SNS-PFEM for granular mass–water large deformation problems

  2025cites this paper
• 3D surface defect detection and measurement using point cloud unwrapping via dimension reduction

  2025cites this paper
• A Particle Finite Element Method for investigating the influence of material and process parameters in 3D Concrete Printing

  2025cites this paper
• Restoration with Base Point Prediction for Deep Point Cloud Geometry Compression

  2025cites this paper
• FloorplanQA: A Benchmark for Spatial Reasoning in LLMs using Structured Representations

  2025cites this paper
• Atomistic Simulation of Thermoinduced Structural Transformations in Four-Component Cu–Au–Pt–Pd Nanoalloys with Different Morphologies

  2025cites this paper
• Multimodal HD Mapping for Intersections by Intelligent Roadside Units

  2025cites this paper
• Large-eddy simulation of the fluid–structure interaction in aquatic canopies consisting of highly flexible blades

  2025cites this paper
• Carvable packing of revolved 3D objects for subtractive manufacturing

  2025cites this paper
• Multi-scale elastic contour mapping for deformable object shape control

  2025cites this paper
• Particle Virtual Element Method (PVEM): an agglomeration technique for mesh optimization in explicit Lagrangian free-surface fluid modelling

  2025cites this paper
• Topological potentials guiding protein self-assembly

  2025cites this paper
• Adaptive RL-BPA framework: Accurate surface reconstruction for tunnel construction using inhomogeneous point cloud

  2025cites this paper
• Adaptively sampled distance functions: A unifying digital twin representation for advanced manufacturing

  2025cites this paper
• Decoupling the effects of topographical roughness and oxidation on the interfacial properties of carbon fiber-epoxy composites

  2025cites this paper
• Percolation transition in entangled granular networks

  2025cites this paper
• Physical simulation method for meteoroid atmospheric entry with multiple-peaked light curves

  2025cites this paper
• Lightweight triangular mesh deformable reconstruction for low quality 3D organ models: Thickness noise and uneven topology

  2025cites this paper
• Lightweight design of mountaineering protection gear: Procedure, Optimization, and Testing

  2025cites this paper
• An algorithm for voxelised solids representation using chain codes

  2025cites this paper
• Spatial scale effect of homogeneous cavitation in liquid aluminum

  2025cites this paper
• Faraday Cage Estimation of Normals for Point Clouds and Ribbon Sketches

  2025cites this paper
• An implicit nodal integration-based three-dimensional particle finite element model for simulating dynamic saturated porous media

  2025cites this paper
• Bridge scour morphology identification and reconstruction using 3D sonar point cloud data

  2025cites this paper
• One-way coupled Eulerian-Lagrangian strategy for wave propagation and impact on coastal areas

  2025cites this paper
• Modelling rockbursts around a deep tunnel based on the particle finite element method: From progressive degradation to catastrophic ejection

  2025cites this paper
• 基于孔洞约束和层次化定位的窗户检测方法

  2025cites this paper
• Exploration of High-Dimensional Performance Spaces via Clustering

  2025cites this paper
• Automatic target spraying and field evaluation of unstructured orchard based on millimeter-wave radar

  2025cites this paper
• Three-Dimensional Crack Quantification Using Fused LiDAR Data and Optical Images

  2025cites this paper
• Stressful Tree Modeling: Breaking Branches with Strands

  2025cites this paper
• Topology-based machine learning for predicting curvature effects in metal-nitrogen-carbon single-atom catalysts

  2025cites this paper
• VoxFall: Non-parametric volumetric change detection for rockfalls

  2025cites this paper
• Design and control optimization for hybrid-controlled overconstrained cable-driven parallel robots

  2025cites this paper
• An Automatic Method for Powerline Extraction From ALS Point Cloud of Powerline Corridors

  2025cites this paper
• VRSurf: Surface Creation from Sparse, Unoriented 3D Strokes

  2025cites this paper
• DrivAer Transformer: A high-precision and fast prediction method for vehicle aerodynamic drag coefficient based on the DrivAerNet++ dataset

  2025cites this paper
• TSGS: Improving Gaussian Splatting for Transparent Surface Reconstruction via Normal and De-lighting Priors

  2025cites this paper
• Point Cloud Normal Estimation Algorithm Based on Point Pair Distance Differences

  2025cites this paper
• Maximum Betti Numbers of Čech Complexes

  2025cites this paper
• Quantitatively analyzing funneling and other characteristics of pedestrian bi-directional flows using rasterization and alpha shapes

  2025cites this paper
• Spatial analysis identifies DC niches as predictors of pembrolizumab therapy in head and neck squamous cell cancer

  2025cites this paper
• Designer artificial environments for membrane protein synthesis

  2025cites this paper
• Rhomboid Tiling for Geometric Graph Deep Learning

  2025cites this paper
• Measurement of drilling parameters in complex structured workpieces using a clustering method of boundary points based on shrinking neighborhood circles

  2025cites this paper
• Circuits in a Box: Computing High-Dimensional Performance Spaces for Analog Integrated Circuits

  2025cites this paper
• ConDT: A 2D curve reconstruction algorithm based on a constrained neighbor proximity graph

  2025cites this paper
• A partitioned Lagrangian finite element approach for the simulation of viscoelastic and elasto-viscoplastic free-surface flows

  2025cites this paper
• Assessing Lagrangian coherence in atmospheric blocking

  2025cites this paper
• DreamCS: Geometry-Aware Text-to-3D Generation with Unpaired 3D Reward Supervision

  2025cites this paper
• Prediction of time-varying instantaneous material removal volume with point cloud contour-filling model in milling process

  2025cites this paper
• Progress and prospect of particle finite element method for large deformation simulation in geotechnical engineering

  2025cites this paper
• Shock wave energy absorption via structural phase transition and bond breakage in metal-organic frameworks.

  2025cites this paper
• D-LaMa: Depth Inpainting of Perspective-Occluded Environments

  2025cites this paper