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

concrete complexityconvex hullDirichlet cellefficient algorithmLaguerre metricpower diagramVoronoi diagram

Mathematics Subject Classification ID

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

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)

• A second-order accurate material-order-independent interface reconstruction technique for multi-material flow simulations
• Approximation of smooth convex bodies by circumscribed polytopes with respect to the surface area
• Finding extreme points in three dimensions and solving the post-office problem in the plane
• Generalized Dirichlet tesselations
• The one-dimensional weighted Voronoi diagram
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Voronoi diagrams and arrangements
• A criterion for the affine equivalence of cell complexes in \(R^ d\) and convex polyhedra in \(R^{d+1}\)
• Edge-skeletons in arrangements with applications
• Recognising polytopical cell complexes and constructing projection polyhedra
• Computing the volume of the union of spheres
• On the geodesic Voronoi diagram of point sites in a simple polygon
• Decomposing trimmed surfaces using the Voronoï diagram and a scan line algorithm
• An axiomatic approach to Voronoi-diagrams in 3D
• Points and triangles in the plane and halving planes in space
• On \(k\)-sets in arrangements of curves and surfaces
• A convex hull algorithm for discs, and applications
• On the complexity of a single cell in certain arrangements of surfaces related to motion planning
• Duality, sections and projections of certain euclidean tilings
• Randomized incremental construction of simple abstract Voronoi diagrams in 3-space
• The error of polytopal approximation with respect to the symmetric difference metric and the \(L_p\) metric
• Improving continuity of Voronoi-based interpolation over Delaunay spheres
• On optimal bridges between two convex regions
• Bumpy pyramid folding
• Delaunay meshing of piecewise smooth complexes without expensive predicates
• Surface parameterization based on polar factorization
• An LP-based k-means algorithm for balancing weighted point sets
• Constrained clustering via diagrams: a unified theory and its application to electoral district design
• An obstruction to Delaunay triangulations in Riemannian manifolds
• Differentiation and regularity of semi-discrete optimal transport with respect to the parameters of the discrete measure
• Worst-case demand distributions in vehicle routing
• Robot motion planning and the single cell problem in arrangements
• Dynamic maintenance and visualization of molecular surfaces.
• On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes
• Incremental topological flipping works for regular triangulations
• Convex hulls of spheres and convex hulls of disjoint convex polytopes
• On computing the convex hull of (piecewise) curved objects
• Three-dimensional convex hull as a fruitful source of diagrams
• Data-driven selection of tessellation models describing polycrystalline microstructures
• Generalised primal-dual grids for unstructured co-volume schemes
• Volume approximations of strongly pseudoconvex domains
• On the estimation of the medial axis and inner parallel body
• Generation of statistically representative microstructures with direct grain geometry control
• Multivariate ranks and quantiles using optimal transport: consistency, rates and nonparametric testing
• Partial optimal transport for a constant-volume Lagrangian mesh with free boundaries
• The singularity set of optimal transportation maps
• A boundary-partition-based Voronoi diagram of \(d\)-dimensional balls: definition, properties, and applications
• Efficient representation of Laguerre mosaics with an application to microstructure simulation of complex ore
• Secondary polytope and secondary power diagram
• Existence and hardness of conveyor belts
• Convergence rates for discretized Monge-Ampère equations and quantitative stability of optimal transport
• A comparative study of interface reconstruction methods for multi-material ALE simulations
• A team-based deployment approach for heterogeneous mobile sensor networks
• Laguerre Voronoi diagram as a model for generating the tessellation patterns on the sphere
• Delaunay simplices in diagonally distorted lattices
• Poisson-Delaunay mosaics of order \(k\)
• On the complexity of randomly weighted multiplicative Voronoi diagrams
• Constructive solution of inverse parametric linear/quadratic programming problems
• Voronoi diagrams over dynamic scenes
• Euclidean Voronoi diagrams of 3D spheres and applications to protein structure analysis
• A numerical method for interface reconstruction of triple points within a volume tracking algorithm
• Power diagram detection with applications to information elicitation
• The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation
• Axioms for Euclidean preferences with a valence dimension
• Manifold reconstruction using tangential Delaunay complexes
• Matching edges and faces in polygonal partitions
• Computing power indices: multilinear extensions and new characterizations
• Volume approximation of smooth convex bodies by three-polytopes of restricted number of edges
• General-dimensional constrained Delaunay and constrained regular triangulations. I: Combinatorial properties
• The predicates of the Apollonius diagram: algorithmic analysis and implementation
• Boat-sail Voronoi diagram and its computation based on a cone-approximation scheme
• Algorithms for hierarchical power
• A new implementation of the geometric method for solving the Eady slice equations
• Second-order characteristics of the edge system of random tessellations and the PPI value of foams
• An efficient algorithm for construction of the power diagram from the voronoi diagram in the plane
• Fully inverse parametric linear/quadratic programming problems via convex liftings
• Power particles: an incompressible fluid solver based on power diagrams
• BULL! -- the molecular geometry engine based on Voronoi diagram, quasi-triangulation, and beta-complex
• Computing the optimal bridge between two convex polygons
• Fitting spherical Laguerre Voronoi diagrams to real-world tessellations using planar photographic images
• The Morse theory of Čech and Delaunay complexes
• Far-field reflector problem and intersection of paraboloids
• Fitting three-dimensional Laguerre tessellations to foam structures
• Revisiting hyperbolic Voronoi diagrams in two and higher dimensions from theoretical, applied and generalized viewpoints
• 3/4-discrete optimal transport
• Practical application of the stochastic finite element method
• scientific article; zbMATH DE number 7499212 (Why is no real title available?)
• A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams
• OPTIMAL VORONOI DIAGRAM CONSTRUCTION WITH n CONVEX SITES IN THREE DIMENSIONS
• Power diagrams and interaction processes for unions of discs
• FARAWAY POINT: A SENTINEL POINT FOR DELAUNAY COMPUTATION
• Random Laguerre tessellations
• Shapes of Delaunay Simplexes and Structural Analysis of Hard Sphere Packings
• The β-Shape and β-Complex for Analysis of Molecular Structures
• BOAT-SAIL VORONOI DIAGRAM AND ITS APPLICATION
• Improved algorithms for discs and balls using power diagrams
• Topological relations between separating circles
• Centroidal Voronoi tessellation in universal covering space of manifold surfaces
• Asymptotic approximation of smooth convex bodies by general polytopes
• Semidual regularized optimal transport

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)