Voronoi Diagrams

1 Partially supported by the Deutsche Forschungsgemeinschaft, grant Kl 655 2-2.

• Publication year

  2021

• Venue

  Handbook of Computational Geometry

• Publication date

  2021-11-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/b978-044482537-7/50006-1
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The upper envelope of piecewise linear functions: Algorithms and applications

  2015cited by this paper
• Properties of Gabriel Graphs Relevant to Geographic Variation Research and the Clustering of Points in the Plane

  2010cited by this paper
• Voronoi Diagrams

  2002cited by this paper
• A lower bound on Voronoi diagram complexity

  2002cited by this paper
• Randomized Algorithms in Computational Geometry

  2000cited by this paper
• Voronoi Diagrams of Line Segments Made Easy * ( Extended

  1999cited by this paper
• Computational geometry: algorithms and applications

  1997cited by this paper
• Randomized Incremental Construction of Simple Abstract Voronoi Diagrams in 3-space

  1997cited by this paper
• Approaching the largest β-skeleton within a minimum weight triangulation

  1996cited by this paper
• On computing Voronoi diagrams by divide-prune-and-conquer

  1996cited by this paper
• Developing a practical projection-based parallel Delaunay algorithm

  1996cited by this paper
• Triangulations intersect nicely

  1996cited by this paper
• Finding Hamiltonian Cycles in Delaunay Triangulations Is NP-complete

  1996cited by this paper
• Quasi-greedy triangulations approximating the minimum weight triangulation

  1996cited by this paper
• A Novel Type of Skeleton for Polygons

  1995cited by this paper
• Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three

  1995cited by this paper
• A comparison of sequential Delaunay triangulation algorithms

  1995cited by this paper
• Voronoi diagrams of lines in 3-space under polyhedral convex distance functions

  1995cited by this paper
• Finding the Medial Axis of a Simple Polygon in Linear Time

  1995cited by this paper
• Efficient Computation of the Geodesic Voronoi Diagram of Points in a Simple Polygon (Extended Abstract)

  1995cited by this paper
• Simple Randomized Algorithms for Closest Pair Problems

  1995cited by this paper
• The Voronoi Diagram of Curved Objects

  1995cited by this paper
• Fast Skeleton Construction

  1995cited by this paper
• The First Subquadratic Algorithm for Complete Linkage Clustering

  1995cited by this paper
• Using the Voronoi tessellation for grouping words and multipart symbols in documents

  1995cited by this paper
• Straight skeletons for general polygonal figures

  1995influential reference
• Voronoi diagrams and containment of families of convex sets on the plane

  1995cited by this paper
• 3D modeling using the Delaunay triangulation

  1995cited by this paper
• Expected case analysis of {221}-skeletons with applications to the construction of minimum-weight triangulations

  1995cited by this paper
• Algorithms for Proximity Problems in Higher Dimensions

  1995cited by this paper
• Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions

  1995cited by this paper
• Optimal parallel randomized algorithms for the Voronoi diagram of line segments in the plane and related problems

  1994cited by this paper
• Empty-shape triangulation algorithms

  1994cited by this paper
• Computing a Subgraph of the Minimum Weight Triangulation

  1994cited by this paper
• On Voronoi Diagrams in the L_p-Metric in Higher Dimensions

  1994cited by this paper
• Introduction to the theory of neural computation

  1994cited by this paper
• Three-dimensional alpha shapes

  1994cited by this paper
• Application of weighted Voronoi diagrams and randomization to variance-based k-clustering

  1994cited by this paper
• Optimality of the Delaunay triangulation in ℝd

  1994influential reference
• How to Compute the Voronoi Diagram of Line Segments: Theoretical and Experimental Results

  1994cited by this paper
• The Delaunay Triangulation Maximizes the Mean Inradius

  1994cited by this paper
• A Linear-time Construction of the Relative Neighborhood Graph From the Delaunay Triangulation

  1994cited by this paper
• Constructing levels in arrangements and higher order Voronoi diagrams

  1994cited by this paper
• Computational geometry - an introduction through randomized algorithms

  1993cited by this paper
• CONVEX DISTANCE FUNCTIONS IN 3-SPACE ARE DIFFERENT

  1993cited by this paper
• The union of balls and its dual shape

  1993cited by this paper
• Tentative prune-and-search for computing Voronoi vertices

  1993cited by this paper
• Piecewise linear paths among convex obstacles

  1993cited by this paper
• Shortest paths among obstacles in the plane

  1993cited by this paper
• Robust Construction of the Voronoi Diagram of a Polyhedron

  1993cited by this paper
• Three-dimensional reconstruction of complex shapes based on the Delaunay triangulation

  1993cited by this paper
• Efficiently updating constrained Delaunay triangulations

  1993cited by this paper
• A linear-time randomized algorithm for the bounded Voronoi diagram of a simple polygon

  1993cited by this paper
• Backwards Analysis of Randomized Geometric Algorithms

  1993cited by this paper
• An optimal convex hull algorithm in any fixed dimension

  1993cited by this paper
• Guaranteed-quality mesh generation for curved surfaces

  1993cited by this paper
• Almost tight upper bounds for lower envelopes in higher dimensions

  1993influential reference
• Randomized Incremental Construction of Abstract Voronoi Diagrams

  1993cited by this paper
• A compact piecewise-linear voronoi diagram for convex sites in the plane

  1993influential reference
• Tighter Bounds on Voronoi Diagrams of Moving Points

  1993cited by this paper
• Zur Konstruktion abstrakter Voronoidiagramme

  1993cited by this paper
• On the topological shape of planar Voronoi diagrams

  1993cited by this paper
• On the Randomized Construction of the Delaunay Tree

  1993cited by this paper
• An O(n2 log n) Time Algorithm for the Minmax Angle Triangulation

  1992cited by this paper
• Classes of graphs which approximate the complete euclidean graph

  1992cited by this paper
• Randomization yields simple O(n log* n) algorithms for difficult Omega(n) problems

  1992cited by this paper
• Minkowski-type theorems and least-squares partitioning

  1992cited by this paper
• New sparseness results on graph spanners

  1992cited by this paper
• Simple algorithms for enumerating interpoint distances and finding $k$ nearest neighbors

  1992cited by this paper
• Numerical stability of algorithms for 2D Delaunay triangulations

  1992cited by this paper
• MESH GENERATION AND OPTIMAL TRIANGULATION

  1992cited by this paper
• Four Results on Randomized Incremental Constructions

  1992cited by this paper
• Applications of random sampling to on-line algorithms in computational geometry

  1992cited by this paper
• Minimal roughness property of the Delaunay triangulation: a shorter approach

  1992cited by this paper
• A subexponential bound for linear programming

  1992cited by this paper
• Optimal two-dimensional triangulations

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

  1992influential reference
• Manhattonian proximity in a simple polygon

  1992cited by this paper
• An upper bound for conforming Delaunay triangulations

  1992cited by this paper
• Recognizing Voronoi Diagrams with Linear Programming

  1992cited by this paper
• Randomization Yields Simple O(n Log ? N) Algorithms for Difficult (n) Problems

  1992cited by this paper
• Construction of the Voronoi diagram for 'one million' generators in single-precision arithmetic

  1992cited by this paper
• Finding k Points with Minimum Diameter and Related Problems

  1991cited by this paper
• A quadratic time algorithm for the minmax length triangulation

  1991cited by this paper
• On Computing the Voronoi Diagram for Restricted Planar Figures

  1991cited by this paper
• Smallest enclosing disks (balls and ellipsoids)

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

  1991cited by this paper
• Voronoi diagrams—a survey of a fundamental geometric data structure

  1991influential reference
• Geometric Clusterings

  1991influential reference
• A sparse graph almost as good as the complete graph on points inK dimensions

  1991cited by this paper
• A Sweepline Algorithm for Generalized Delaunay Triangulations

  1991cited by this paper
• REAL ALGEBRAIC AND SEMI‐ALGEBRAIC SETS (Actualités Mathématiques 348)

  1991cited by this paper
• Optimality of the Delaunay triangulation in Rd

  1991cited by this paper
• GEOMPACK — a software package for the generation of meshes using geometric algorithms☆

  1991cited by this paper
• The upper envelope of voronoi surfaces and its applications

  1991cited by this paper
• An O(n log² h) Time Algorithm for the Three-Dimensional Convex Hull Problem

  1991cited by this paper
• A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams

  1991cited by this paper
• On levels in arrangements and voronoi diagrams

  1991cited by this paper
• Small-dimensional linear programming and convex hulls made easy

  1991cited by this paper
• On the Zone Theorem for Hyperplane Arrangements

  1991cited by this paper

• Delaunay Triangulations with Predictions

  2026cites this paper
• Inversion of geotechnical parameters based on improved adaptive sequential sampling method and surrogate model

  2026cites this paper
• VERNE: A Spatial Data Structure Representing Railway Networks for Autonomous Robot Navigation

  2026cites this paper
• On basic $r$-ball polyhedra

  2026cites this paper
• Dynamic Path Optimization of Humanoid Welding Robots Based on Environmental Modeling and Real-Time Obstacle Detection

  2026cites this paper
• Applicability of pore boundary tessellation for quantitative characterization of pore evolution of binder jet 3D printed and sintered metal microstructures: A Ni-Mn-Ga case study and literature validation.

  2025cites this paper
• Dynamic data visualizations as events: effects of framing and change salience on segmenting dynamic maps

  2025cites this paper
• Computational design of 3D printed flexible Voronoi lattices

  2025cites this paper
• A Morse Transform for Drug Discovery

  2025cites this paper
• Neural 3D Face Shape Stylization Based on Single Style Template via Weakly Supervised Learning

  2025cites this paper
• Single‐Shot Example Terrain Sketching by Graph Neural Networks

  2025cites this paper
• Efficient heuristics for the obnoxious planar p-median problem with variable sizes

  2025cites this paper
• MTvis: Understanding and Optimizing Microbial Time-series Data Augmentation Model via Interactive Visualization

  2025cites this paper
• Training-Free Geospatial Place Representation Learning from Large-Scale Point-of-Interest Graph Data

  2025cites this paper
• 3D spatial coverage by elliptical beams for neighbor discovery in directional flying ad hoc networks

  2025cites this paper
• Functions and inequalities associated with the nonconvex second-order cone

  2025cites this paper
• Particle tracking velocimetry study of wet particle flow in a pseudo two-dimensional fluidized bed

  2025cites this paper
• Machine learning for modelling unstructured grid data in computational physics: a review

  2025cites this paper
• Sums of Wedges: Conforming Weighted Delaunay Triangulations are Polynomial in Fixed Dimension

  2025cites this paper
• A comparative study of two methods for estimating aluminum agglomerate sizes: Cohen's pocket model and density-based clustering

  2025cites this paper
• SemanticStitch: enhancing image coherence through foreground-aware seam carving

  2025cites this paper
• Product Recognition for Inventory Management Using Spatial Partitioning in a Multi-Camera System

  2025cites this paper
• Efficient top-k spatial-range-constrained approximate nearest neighbor search on geo-tagged high-dimensional vectors

  2025cites this paper
• Cross-feeding percolation phase transitions of intercellular metabolic networks

  2025cites this paper
• Voronoi-grid-based Pareto Front Learning and Its Application to Collaborative Federated Learning

  2025cites this paper
• MEDTEG (Minimum Entropy Dynamic Test Grids): A Novel Algorithm for Adding New Test Locations to a Perimetric Test Grid

  2025cites this paper
• A Framework for PCB Design File Reconstruction from X-Ray CT Annotations

  2025cites this paper
• Fast and Accurate Reconstruction of Voronoi Generators in Large Tessellations

  2025influential citation
• Travel-time accessibility and adaptive spatial planning solutions for the healthcare system

  2025cites this paper
• AnchorGK: Anchor-based Incremental and Stratified Graph Learning Framework for Inductive Spatio-Temporal Kriging

  2025cites this paper
• Few-Shot Meta Spectral Clustering with knowledge reuse

  2025cites this paper
• DCFO: Density-Based Counterfactuals for Outliers - Additional Material

  2025cites this paper
• VQCounter: Designing Visual Prompt Queue for Accurate Open-World Counting

  2025cites this paper
• An RSFQ Physical Synthesis Framework for Superconductor 3-D Logic Process

  2025cites this paper
• An Enhanced Model-based Approach for Short Text Clustering

  2025cites this paper
• Advanced PTSVM Based Breast Cancer Classification with Weighted Feature Selection

  2024cites this paper
• Review of Fast Computation Methods for Finite-State Predictive Control of Multi-Phase Drives

  2024cites this paper
• A distributed framework for multiple UAV cooperative target search under dynamic environment

  2024cites this paper
• Pseudo Training Data Generation for Unsupervised Cell Membrane Segmentation in Immunohistochemistry Images

  2024cites this paper
• Visualizing fractional inequalities through 2D and 3D graphs with applications

  2024cites this paper
• Nested Wave Function Collapse Enables Large-Scale Content Generation

  2024cites this paper
• Data-Driven Reachability Analysis for Nonlinear Systems

  2024cites this paper
• Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction

  2024cites this paper
• D4G framework: a novel Voronoi diagram classification for decoding natural geometrics to enhance the built environment

  2024influential citation
• Seam Mask Guided Partial Reconstruction with Quantum-Inspired Local Aggregation For Deep Image Stitching

  2024cites this paper
• Efficient energy aware area coverage in WSNs: a 2L-Voronoi guided PSO approach

  2024cites this paper
• Bio2Token: All-atom tokenization of any biomolecular structure with Mamba

  2024cites this paper
• Solution-Hashing Search Based on Layout-Graph Transformation for Unequal Circle Packing

  2024cites this paper
• Dynamical system prediction from sparse observations using deep neural networks with Voronoi tessellation and physics constraint

  2024cites this paper
• The Sound of Silence: Exploiting Information From the Lack of Communication

  2024cites this paper
• An adaptive-size vector tile pyramid construction method considering spatial data distribution density characteristics

  2024cites this paper
• Distributed Maze Exploration Using Multiple Agents and Optimal Goal Assignment

  2024cites this paper
• Numerical simulation of seasonal underground hydrogen storage: Role of the initial gas amount on the round-trip hydrogen recovery efficiency

  2024cites this paper
• Solving Pursuer-Evader Robot Game Strategies via Optimised Graphical Voronoî Technique

  2024cites this paper
• Quasi-random Fractal Search (QRFS): A dynamic metaheuristic with sigmoid population decrement for global optimization

  2024cites this paper
• Demand Equilibria in Spatial Service Systems

  2024cites this paper
• Design of three-dimensional binary manipulators for pick-and-place task avoiding obstacles

  2024cites this paper
• Decoding Urban Intelligence: Clustering and Feature Importance in Smart Cities

  2024cites this paper
• Occupation-aware planning method for robotic monitoring missions in dynamic environments

  2024cites this paper
• MTCSNet: One-Stage Learning and Two-Point Labeling are Sufficient for Cell Segmentation

  2024cites this paper
• A Comprehensive Survey on Delaunay Triangulation: Applications, Algorithms, and Implementations Over CPUs, GPUs, and FPGAs

  2024cites this paper
• The Effect of the Contemporary Digital Revolution on the Forms of Metal Furniture and Construction Products

  2024cites this paper
• Shock-induced phase transition and damage in nano-polycrystalline graphite affected by grain boundaries

  2024cites this paper
• Revealing Incomplete Data through Scientific Visualizations in an Immersive Dome Experience

  2024cites this paper
• 3D-IC Power Distribution Network (PDN) Impedance Prediction using Deep Learning (DL)

  2023cites this paper
• PowerRTF: Power Diagram based Restricted Tangent Face for Surface Remeshing

  2023cites this paper
• Extend Wave Function Collapse Algorithm to Large-Scale Content Generation

  2023cites this paper
• Development of a Ka-Band Non-Regular Multibeam Coverage Antenna

  2023cites this paper
• Resilient Localization and Coverage in the Internet of Things

  2023cites this paper
• Research on Micromechanical Behavior of Current Collector of Lithium-Ion Batteries Battery Cathode during the Calendering Process

  2023cites this paper
• Integer Point Enumeration in Multi-Dimensional Geometric Objects with FPGA Acceleration

  2023cites this paper
• Morphological characterization and reconstruction of fractured heat-treated glass

  2023cites this paper
• Towards a Persistence Diagram that is Robust to Noise and Varied Densities

  2023cites this paper
• A quantitative evaluation model of ancient military defense efficiency based on spatial strength—take Zhejiang of the Ming Dynasty as an example

  2023cites this paper
• Automated Generation of Site Map Graphs for Robot-Inclusive Tactile Marker Placement

  2023cites this paper
• Design of Three-Dimensional Binary Manipulators Based on the KS Statistic and Maximum Empty Circles

  2023cites this paper
• Modelling the fracture behaviour of polycrystalline columnar ice using the grain-based discrete element method

  2023cites this paper
• Socioeconomic reorganization of communication and mobility networks in response to external shocks

  2023cites this paper
• Wind dynamic and energy-efficiency path planning for unmanned aerial vehicles in the lower-level airspace and urban air mobility context

  2023cites this paper
• Deep learning-based segmentation, quantification and modeling of expansive soil cracks

  2023cites this paper
• Crown-Level Structure and Fuel Load Characterization from Airborne and Terrestrial Laser Scanning in a Longleaf Pine (Pinus palustris Mill.) Forest Ecosystem

  2023cites this paper
• Quadrotor Path Planning and Polynomial Trajectory Generation Using Quadratic Programming for Indoor Environments

  2023cites this paper
• An inverse modeling method to estimate undertain spatial configurations from 2d information and time-based visual discriminations

  2023cites this paper
• Multi-Target Pursuit by a Decentralized Heterogeneous UAV Swarm using Deep Multi-Agent Reinforcement Learning

  2023cites this paper
• Geometry in Our Three-Dimensional World

  2023cites this paper
• Construção Automática de Múltiplas Árvores Circulatórias com Controle de Invasão de Território

  2023cites this paper
• A Smart Spatial Routing and Accessibility Analysis System for EMS Using Catchment Areas of Voronoi Spatial Model and Time-Based Dijkstra’s Routing Algorithm

  2023cites this paper
• DeepFracture: A Generative Approach for Predicting Brittle Fractures with Neural Discrete Representation Learning

  2023cites this paper
• Bio-inspired study of stiffener arrangement in composite stiffened panels using a Voronoi diagram as an indicator

  2023cites this paper
• Fusion of Graph and Tabular Deep Learning Models for Predicting Chronic Kidney Disease

  2023cites this paper
• Increasing Features in MAP-Elites Using an Age-Layered Population Structure

  2023cites this paper
• Vega: Drone-based Multi-Altitude Target Detection for Autonomous Surveillance

  2023cites this paper
• Accelerate microstructure evolution simulation using graph neural networks with adaptive spatiotemporal resolution

  2023influential citation
• Computational Segmentation of Timber Slabs with Free Column Placement

  2023cites this paper
• A topology-based approach to individual tree segmentation from airborne LiDAR data

  2023cites this paper
• Automated Health Estimation of Capsicum annuum L. Crops by Means of Deep Learning and RGB Aerial Images

  2022cites this paper
• An analysis of three-dimensional patterns of experimental detonation cells

  2022cites this paper
• The effect of pore sizes on the elastic behaviour of open-porous cellular materials

  2022cites this paper
• Development of a New Method to Support a Participatory Planning for Piped Water Supply Infrastructure in Informal Settlements

  2022cites this paper
• The convergence of inversive distance circle packings to the Riemann mapping

  2022cites this paper