Power Diagrams: Properties, Algorithms and Applications

DOI10.1137/0216006MaRDI QIDQ4725255zbMATH OpenOpenAlexFDO

Authors Franz Aurenhammer

Publication date 1987

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0216006

zbMATH Keywords

convex hullVoronoi diagramefficient algorithmpower diagramLaguerre metricconcrete complexityDirichlet cell

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Polytopes and polyhedra (52Bxx)

Recommendations

• Improved algorithms for discs and balls using power diagrams
• scientific article; zbMATH DE number 4044614
• Voronoi diagrams and Delaunay triangulations
• An optimal algorithm for constructing the weighted Voronoi diagram in the plane
• scientific article; zbMATH DE number 1835887

Cited in

(only showing first 100 items - show all)

• Volume approximation of smooth convex bodies by three-polytopes of restricted number of edges
• Fitting three-dimensional Laguerre tessellations to foam structures
• 3/4-discrete optimal transport
• Distributed computation of virtual coordinates for greedy routing in sensor networks
• Generation of statistically representative microstructures with direct grain geometry control
• Computing power indices: multilinear extensions and new characterizations
• Convergence rates for discretized Monge-Ampère equations and quantitative stability of optimal transport
• Volume approximations of strongly pseudoconvex domains
• scientific article; zbMATH DE number 7499212 (Why is no real title available?)
• The predicates of the Apollonius diagram: algorithmic analysis and implementation
• Improved algorithms for discs and balls using power diagrams
• Data-driven selection of tessellation models describing polycrystalline microstructures
• An axiomatic approach to Voronoi-diagrams in 3D
• A convex hull algorithm for discs, and applications
• On optimal bridges between two convex regions
• Asymptotics for semidiscrete entropic optimal transport
• The β-Shape and β-Complex for Analysis of Molecular Structures
• MULTIPLE PARAMETER CONTINUATION: COMPUTING IMPLICITLY DEFINED k-MANIFOLDS
• Second-order characteristics of the edge system of random tessellations and the PPI value of foams
• A comparative study of interface reconstruction methods for multi-material ALE simulations
• The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation
• Boat-sail Voronoi diagram and its computation based on a cone-approximation scheme
• Computing the volume of the union of spheres
• Bumpy pyramid folding
• Polyhedral transformation based on confocal quadratic surface properties. Graphical speculations
• The polyhedral geometry of truthful auctions
• Fully inverse parametric linear/quadratic programming problems via convex liftings
• Generalised primal-dual grids for unstructured co-volume schemes
• An analytical representation of the 2d generalized balanced power diagram
• Bregman Voronoi diagrams
• The Morse theory of Čech and Delaunay complexes
• General-dimensional constrained Delaunay and constrained regular triangulations. I: Combinatorial properties
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Semidual regularized optimal transport
• On the geodesic Voronoi diagram of point sites in a simple polygon
• An efficient algorithm for construction of the power diagram from the voronoi diagram in the plane
• Voronoi diagrams and arrangements
• Asymptotic approximation of smooth convex bodies by general polytopes
• Voronoi diagrams in quasi-2D hard sphere systems
• Rejection- and importance-sampling-based perfect simulation for Gibbs hard-sphere models
• On computing the convex hull of (piecewise) curved objects
• Power diagrams and interaction processes for unions of discs
• On the estimation of the medial axis and inner parallel body
• Randomized incremental construction of abstract Voronoi diagrams
• Convex hulls of spheres and convex hulls of disjoint convex polytopes
• Generalized Dirichlet tesselations
• Computing the optimal bridge between two convex polygons
• Decomposing trimmed surfaces using the Voronoï diagram and a scan line algorithm
• Stable marker-particle method for the Voronoi diagram in a flow field
• Partial optimal transport for a constant-volume Lagrangian mesh with free boundaries
• scientific article; zbMATH DE number 7370561 (Why is no real title available?)
• ON DELETION IN DELAUNAY TRIANGULATIONS
• Axioms for Euclidean preferences with a valence dimension
• On the construction of abstract Voronoi diagrams
• Mathematical analysis and calculation of molecular surfaces
• Randomized incremental construction of simple abstract Voronoi diagrams in 3-space
• scientific article; zbMATH DE number 7651184 (Why is no real title available?)
• TERRAIN VISIBILITY WITH MULTIPLE VIEWPOINTS
• Wasserstein distance and the distributionally robust TSP
• Centroidal Voronoi tessellation in universal covering space of manifold surfaces
• Voronoi Diagrams for Parallel Halflines and Line Segments in Space
• Power particles: an incompressible fluid solver based on power diagrams
• Incremental topological flipping works for regular triangulations
• Poisson-Delaunay mosaics of order \(k\)
• Far-field reflector problem and intersection of paraboloids
• Perturbations for Delaunay and weighted Delaunay 3D triangulations
• Surface parameterization based on polar factorization
• Random Laguerre tessellations
• A mean-strain estimate for plastic particles intended for distinct-particle simulations at high relative density
• Radius functions on Poisson-Delaunay mosaics and related complexes experimentally
• Regular triangulations and Steiner points
• Fast and efficient computation of additively weighted Voronoi cells for applications in molecular biology
• Dynamic maintenance and visualization of molecular surfaces.
• Microstructure characterization and stochastic modeling of open‐cell foam based on μCT‐image analysis
• On the complexity of a single cell in certain arrangements of surfaces related to motion planning
• Delaunay simplices in diagonally distorted lattices
• Existence and hardness of conveyor belts
• The Singularity Set of Optimal Transportation Maps
• Weighted triangulations for geometry processing
• Voronoi diagrams over dynamic scenes
• Delaunay meshing of piecewise smooth complexes without expensive predicates
• Points and triangles in the plane and halving planes in space
• Randomized incremental construction of simple abstract Voronoi diagrams in 3-space
• A second-order accurate material-order-independent interface reconstruction technique for multi-material flow simulations
• FARAWAY POINT: A SENTINEL POINT FOR DELAUNAY COMPUTATION
• Geometric clustering for the consolidation of farmland and woodland
• Improving continuity of Voronoi-based interpolation over Delaunay spheres
• Construction of Voronoi diagrams in the plane by using maps
• On clustering induced Voronoi diagrams
• Extension of the edge tracing algorithm to disconnected Voronoi skeletons
• On soft power diagrams
• Practical application of the stochastic finite element method
• A criterion for the affine equivalence of cell complexes in \(R^ d\) and convex polyhedra in \(R^{d+1}\)
• Constructive solution of inverse parametric linear/quadratic programming problems
• Optimal Transport Approximation of 2-Dimensional Measures
• Single-particle fabric tensors for assemblies of spherical particles
• A time-optimal parallel algorithm for the computing of Voronoi-diagrams
• The transport map computed by iterated function system
• Accelerating surface remeshing through GPU-based computation of the restricted tangent face
• Concurrent adaptive mass-conserving comminution of granular materials using rigid elements

This page was built for publication: Power Diagrams: Properties, Algorithms and Applications

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