On the shape of a set of points in the plane

1983/07/01 by H. Edelsbrunner, Herbert Edelsbrunner, D. Kirkpatrick +3 · 70 citations
Computer Science · Business, Management and Accounting · Social Sciences · #Computational Geometry and Mesh Generation #Facility Location and Emergency Management #Geographic Information Systems Studies

paper · doi:10.1109/tit.1983.1056714

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, " <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">α</tex> -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 optimal <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(n log n)</tex> algorithm that constructs <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">α</tex> -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
• Distributed Spatial Data Clustering as a New Approach for Big Data\n Analysis
• Set estimation from reflected Brownian motion
• Room Detection for Topological Maps
• 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

• Three-dimensional alpha shapes
• A 3D Sweep Hull Algorithm for computing Convex Hulls and Delaunay\n Triangulation
• Delaunay Triangulations of Points on Circles
• A weak definition of Delaunay triangulation
• A Simple Convex Layers Algorithm