On the shape of a set of points in the plane
1983/07/01 by H. Edelsbrunner, Herbert Edelsbrunner, D. Kirkpatrick +3 · 1,853 citations
Business, Management and Accounting · Computer Science · Mathematics · Social Sciences · #Algorithm #Artificial intelligence #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Convex hull #Delaunay triangulation #Discrete mathematics #Facility Location and Emergency Management #Generalization #Geographic Information Systems Studies #Geometry #Mathematical analysis #Mathematics #Plane (geometry) #Point (geometry) #Regular polygon #Set (abstract data type)
paper · doi:10.1109/tit.1983.1056714
published in IEEE Transactions on Information Theory 29(4), 551-559 (Institute of Electrical and Electronics Engineers)
openalex publication_date 1983/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Abstract
A generalization of the convex hull of a finite set of points in the plane is introduced and analyzed. This generalization leads to a family of straight-line graphs, "α-shapes," which seem to capture the intuitive notions of "fine shape" and "crude shape" of point sets. It is shown that a-shapes are subgraphs of the closest point or furthest point Delaunay triangulation. Relying on this result an optimalO(n log n)algorithm that constructsα-shapes is developed.
Cited by
- Boundary recognition of ship planar components from point clouds based on trimmed delaunay triangulation
- A distance-based parameter free algorithm for curve reconstruction
- Path integrals in the theory of condensed helium
- Estimating 3D individual tree crown growth using multi-temporal LiDAR
- Emergence of Hexanematic Order in a Growing Confluent Cell Monolayer
- Neural Surface and Reflectance Modelling from 3D Radar Data
- 3DPipe: A Pipelined GPU Framework for Scalable Generalized Spatial Join over Polyhedral Objects
- A Survey of Methods for Constructing 3D Urban Models From Point Clouds
- MuSpAn: A Toolbox for Multiscale Spatial Analysis
- Arl8b inactivates the Rab11a recycling pathway to promote LAMP1 sorting and lysosome biogenesis
- Schrödinger's Navigator: Imagining an Ensemble of Futures for Zero-Shot Object Navigation
- OccuFly: A 3D Vision Benchmark for Semantic Scene Completion from the Aerial Perspective
- A Novel Patch-Based TDA Approach for Computed Tomography Imaging
- Dense point sets have sparse Delaunay triangulations
- Persistent Cycle Representatives and Generalized Landscapes for Codimension 1 Persistent Homology
- Primordial non-Gaussianity -- Fast simulations and persistent summary statistics
- Adversarial shape perturbations on 3D point clouds
- Major nuclear locales define nuclear genome organization and function beyond A and B compartments
- Optimizing Robot Positioning Against Placement Inaccuracies: A Study on the Fanuc CRX10iA/L
- Registration-Free Monitoring of Unstructured Point Cloud Data via Intrinsic Geometrical Properties
- URDF-Anything: Constructing Articulated Objects with 3D Multimodal Language Model
- Improved Understanding of How Kinematic and Thermodynamic Environmental Changes Impact Modeled Overshooting Top Characteristics
- Short-term calving front dynamics and mass loss at Sálajiegna glacier, northern Sweden, assessed by uncrewed surface and aerial vehicles
- Expected Length of the Euclidean Minimum Spanning Tree and 1-norms of Chromatic Persistence Diagrams in the Plane
- Context-dependent spatial multicellular network motifs for single-cell spatial biology
- Mobile Coverage Analysis using Crowdsourced Data
- Optimizing Administrative Divisions: A Vertex k-Center Approach for Edge-Weighted Road Graphs
- Fitting 3D Shapes from Partial and Noisy Point Clouds with Evolutionary Computing
- Mathematical modelling reveals cellular dynamics within tumour spheroids
- Spectral Sequences, Exact Couples and Persistent Homology of filtrations
- A global biogeographic regionalization for butterflies
- The Influence of Internal Structure on Physical Outcomes of the 2029 Apophis Close Approach with Earth
- Use of TanDEM-X and Sentinel Products to Derive Gully Activity Maps in Kunene Region (Namibia) Based on Automatic Iterative Random Forest Approach
- FloorSAM: SAM-Guided Floorplan Reconstruction with Semantic-Geometric Fusion
- Area Graph: Generation of Topological Maps using the Voronoi Diagram
- Approximate Cech Complexes in Low and High Dimensions
- Follow My Hold: Hand-Object Interaction Reconstruction through Geometric Guidance
- Typed Topological Structures Of Datasets
- Shape-from-Template with Generalised Camera
- AriEL: volume coding for sentence generation
- Summarizing Classed Region Maps with a Disk Choreme
- Point2Act: Efficient 3D Distillation of Multimodal LLMs for Zero-Shot Context-Aware Grasping
- TrajLens: Visual Analysis for Constructing Cell Developmental Trajectories in Cross-Sample Exploration
- Distributed Spatial Data Clustering as a New Approach for Big Data Analysis
- Set estimation from reflected Brownian motion
- Room Detection for Topological Maps
- Leveraging spatial scale and temporal variation to track the spread rate of invasive spotted lanternflies (Lycorma delicatula)
- Finding the theta-Guarded Region
- Learnable Triangulation for Deep Learning-based 3D Reconstruction of Objects of Arbitrary Topology from Single RGB Images
- Grouping and Recognition of Dot Patterns with Straight Offset Polygons
- Minimax Estimation of the Volume of a Set with Smooth Boundary
- A computational geometry method for the inverse scattering problem
- Representing Data by a Mixture of Activated Simplices
- Sketches of a platypus: persistent homology and its algebraic foundations
- Attribute-based Explanations of Non-Linear Embeddings of High-Dimensional Data
- Fast Computation of Isochrones in Road Networks
- Higher signature Delaunay decompositions
- Mining Points of Interest via Address Embeddings: An Unsupervised Approach
- Learning to flock in open space by avoiding collisions and staying together
- Low-Rank Head Avatar Personalization with Registers
- Stratified Formal Deformations and Intersection Homology of Data Point Clouds
- Topology across Scales on Heterogeneous Cell Data
- CityGo: Lightweight Urban Modeling and Rendering with Proxy Buildings and Residual Gaussians
- Geometry and Morphology of the Cosmic Web: Analyzing Spatial Patterns in the Universe
- Efficient compression of neural networks and datasets
- The union of balls and its dual shape
- Beyond A and B Compartments: how major nuclear locales define nuclear genome organization and function
- DeepPerimeter: Indoor Boundary Estimation from Posed Monocular Sequences
- Solution of the chemical master equation by radial basis functions approximation with interface tracking
- Incremental topological flipping works for regular triangulations
- ReVSI: Rebuilding Visual Spatial Intelligence Evaluation for Accurate Assessment of VLM 3D Reasoning
- Voronoi diagrams—a survey of a fundamental geometric data structure
- Distributed boundary tracking using alpha and Delaunay-Cech shapes
- PolyLayout: Multi-room Manhattan Layout Estimation
- Three-dimensional alpha shapes
- Relative neighborhood graphs and their relatives
- An Optimal Hierarchical Clustering Approach to Mobile LiDAR Point Clouds
- Efficient Large Scale Clustering Based on Data Partitioning
- GeRaF: Neural Geometry Reconstruction from Radio Frequency Signals
- A Low-Cost Photogrammetry System for 3D Plant Modeling and Phenotyping
- Density‐based region search with arbitrary shape for object localisation
- Rhythmicity, Recurrence, and Recovery of Flagellar Beating
- Applications of random sampling in computational geometry, II
- Semantic mapping for orchard environments by merging two‐sides reconstructions of tree rows
- Classical Nucleation Theory Description of Active Colloid Assembly
- A roadmap for the computation of persistent homology
- The topology of the cosmic web in terms of persistent Betti numbers
- The γ-neighborhood graph
- Tree Morphology for Phenotyping from Semantics-Based Mapping in Orchard Environments
- Optimal and suboptimal robust algorithms for proximity graphs
- Molecular shape as a (useful) bias in chemistry
- VibrantLeaves: A principled parametric image generator for training deep restoration models
- Applications of random sampling in computational geometry, II
- Measuring shape with topology
- Data-Driven Molecular Dynamics and TEM Analysis of Crystal Growth and Hydrogen Sensing in Pt-Functionalized Graphene Chemiresistive Sensors
- Beta skeleton [wikipedia]
- Convex hull [wikipedia]
- Intrusion experiments to measure territory size: development of the method, tests through simulations, and application in the frog Allobates femoralis. [europepmc]
- Super-resolution imaging of C-type lectin spatial rearrangement within the dendritic cell plasma membrane at fungal microbe contact sites. [europepmc]
- Extensive range overlap between heliconiine sister species: evidence for sympatric speciation in butterflies? [europepmc]
- An advanced shape-fitting algorithm applied to quadrupedal mammals: improving volumetric mass estimates. [europepmc]
- Emerging Computational Methods for the Rational Discovery of Allosteric Drugs. [europepmc]
- SLICER: inferring branched, nonlinear cellular trajectories from single cell RNA-seq data. [europepmc]
- Measuring cellular traction forces on non-planar substrates. [europepmc]
- Local alignment vectors reveal cancer cell-induced ECM fiber remodeling dynamics. [europepmc]
- Advances in the Development of Shape Similarity Methods and Their Application in Drug Discovery. [europepmc]
- Consensus and uncertainty in the geographic range of Aedes aegypti and Aedes albopictus in the contiguous United States: Multi-model assessment and synthesis. [europepmc]
- Ultra-thin fluorocarbon foils optimise multiscale imaging of three-dimensional native and optically cleared specimens. [europepmc]
- A roadmap for the computation of persistent homology. [europepmc]
- Spinal cord hypermetabolism extends to skeletal muscle in amyotrophic lateral sclerosis: a computational approach to [18F]-fluorodeoxyglucose PET/CT images. [europepmc]
- Mathematical modelling reveals cellular dynamics within tumour spheroids. [europepmc]
- The fate of Meconopsis species in the Tibeto-Himalayan region under future climate change. [europepmc]
- The atomistic details of the ice recrystallisation inhibition activity of PVA. [europepmc]
- Single-atom level determination of 3-dimensional surface atomic structure via neural network-assisted atomic electron tomography. [europepmc]
- General Trends in Core-Shell Preferences for Bimetallic Nanoparticles. [europepmc]
- Cortical thickness systematically varies with curvature and depth in healthy human brains. [europepmc]
- Human-ignited fires result in more extreme fire behavior and ecosystem impacts. [europepmc]
- California wildfire spread derived using VIIRS satellite observations and an object-based tracking system. [europepmc]
- Direct strain correlations at the single-atom level in three-dimensional core-shell interface structures. [europepmc]
- Estimating the Similarity between Protein Pockets. [europepmc]
- Climate change and land use threaten global hotspots of phylogenetic endemism for trees. [europepmc]
- Major nuclear locales define nuclear genome organization and function beyond A and B compartments. [europepmc]
Related