Power Diagrams: Properties, Algorithms and Applications
From MaRDI portal
Publication:4725255
DOI10.1137/0216006zbMath0616.52007OpenAlexW2048475323MaRDI QIDQ4725255
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
power diagramconvex hullVoronoi diagramefficient algorithmLaguerre metricconcrete complexityDirichlet cell
Related Items
Polyhedral Transformation Based on Confocal Quadratic Surface Properties. Graphical Speculations, Fast and efficient computation of additively weighted Voronoi cells for applications in molecular biology, Fitting three-dimensional Laguerre tessellations to foam structures, Asymptotics for Semidiscrete Entropic Optimal Transport, Semidual Regularized Optimal Transport, ON DELETION IN DELAUNAY TRIANGULATIONS, EUCLIDEAN VORONOI DIAGRAM FOR CIRCLES IN A CIRCLE, Regular triangulations and Steiner points, A Shape-Newton Approach to the Problem of Covering with Identical Balls, Revisiting Hyperbolic Voronoi Diagrams in Two and Higher Dimensions from Theoretical, Applied and Generalized Viewpoints, Microstructure characterization and stochastic modeling of open‐cell foam based on μCT‐image analysis, On Clustering Induced Voronoi Diagrams, OPTIMAL VORONOI DIAGRAM CONSTRUCTION WITH n CONVEX SITES IN THREE DIMENSIONS, The polyhedral geometry of truthful auctions, Cellular topology optimization on differentiable Voronoi diagrams, Fitting Spherical Laguerre Voronoi Diagrams to Real-World Tessellations Using Planar Photographic Images, Unnamed Item, The Morse theory of Čech and Delaunay complexes, Unnamed Item, Accelerating surface remeshing through GPU-based computation of the restricted tangent face, Computing the multicover bifiltration, Optimal Transport Approximation of 2-Dimensional Measures, Single-particle fabric tensors for assemblies of spherical particles, Secondary Power Diagram, Dual of Secondary Polytope, A time-optimal parallel algorithm for the computing of Voronoi-diagrams, Asymmetric tropical distances and power diagrams, Power diagrams and interaction processes for unions of discs, Radius Functions on Poisson–Delaunay Mosaics and Related Complexes Experimentally, FARAWAY POINT: A SENTINEL POINT FOR DELAUNAY COMPUTATION, Concurrent Adaptive Mass-Conserving Comminution of Granular Materials Using Rigid Elements, Wasserstein Distance and the Distributionally Robust TSP, Unnamed Item, Random Laguerre tessellations, Abstracted Visualization of Halo Topologies in Dark Matter Simulations, 3/4-Discrete Optimal Transport, Rejection- and importance-sampling-based perfect simulation for Gibbs hard-sphere models, A new duality result concerning Voronoi diagrams, Separable Distance Transformation and Its Applications, An efficient algorithm for the three-dimensional diameter problem, Weighted Triangulations for Geometry Processing, Weighted \({\mathcal A}\)-shape: A descriptor of the shape of a point set, Randomized incremental construction of simple abstract Voronoi diagrams in 3-space, Bregman Voronoi diagrams, Power particles, Weighted Poisson--Delaunay Mosaics, Shapes of Delaunay Simplexes and Structural Analysis of Hard Sphere Packings, The β-Shape and β-Complex for Analysis of Molecular Structures, Good Clusterings Have Large Volume, BOAT-SAIL VORONOI DIAGRAM AND ITS APPLICATION, MULTIPLE PARAMETER CONTINUATION: COMPUTING IMPLICITLY DEFINED k-MANIFOLDS, Asymptotic approximation of smooth convex bodies by general polytopes, Voronoi diagrams in quasi-2D hard sphere systems, TERRAIN VISIBILITY WITH MULTIPLE VIEWPOINTS, The Singularity Set of Optimal Transportation Maps, Voronoi Diagrams for Parallel Halflines and Line Segments in Space, Duality, sections and projections of certain euclidean tilings, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes, Second-order characteristics of the edge system of random tessellations and the PPI value of foams, Constructive solution of inverse parametric linear/quadratic programming problems, Bumpy pyramid folding, Voronoi diagrams and arrangements, Voronoi diagrams over dynamic scenes, A criterion for the affine equivalence of cell complexes in \(R^ d\) and convex polyhedra in \(R^{d+1}\), Multivariate ranks and quantiles using optimal transport: consistency, rates and nonparametric testing, Computing the optimal bridge between two convex polygons, Partial optimal transport for a constant-volume Lagrangian mesh with free boundaries, Edge-skeletons in arrangements with applications, Recognising polytopical cell complexes and constructing projection polyhedra, Far-field reflector problem and intersection of paraboloids, Computing the volume of the union of spheres, 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, Practical application of the stochastic finite element method, A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams, Incremental topological flipping works for regular triangulations, Randomized incremental construction of simple abstract Voronoi diagrams in 3-space, On the geodesic Voronoi diagram of point sites in a simple polygon, Delaunay meshing of piecewise smooth complexes without expensive predicates, The singularity set of optimal transportation maps, Stable marker-particle method for the Voronoi diagram in a flow field, Surface parameterization based on polar factorization, Decomposing trimmed surfaces using the Voronoï diagram and a scan line algorithm, A boundary-partition-based Voronoi diagram of \(d\)-dimensional balls: definition, properties, and applications, General truthfulness characterizations via convex analysis, Topological relations between separating circles, A new implementation of the geometric method for solving the Eady slice equations, Perturbations for Delaunay and weighted Delaunay 3D triangulations, Power diagram detection with applications to information elicitation, Extension of the edge tracing algorithm to disconnected Voronoi skeletons, On soft power diagrams, The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation, 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, Axioms for Euclidean preferences with a valence dimension, Efficient representation of Laguerre mosaics with an application to microstructure simulation of complex ore, Centroidal Voronoi tessellation in universal covering space of manifold surfaces, An obstruction to Delaunay triangulations in Riemannian manifolds, Convex hulls of spheres and convex hulls of disjoint convex polytopes, On computing the convex hull of (piecewise) curved objects, Secondary polytope and secondary power diagram, Energy-efficient paths in radio networks, Existence and hardness of conveyor belts, Manifold reconstruction using tangential Delaunay complexes, A relationship between Gale transforms and Voronoi diagrams, An efficient algorithm for construction of the power diagram from the voronoi diagram in the plane, Differentiation and regularity of semi-discrete optimal transport with respect to the parameters of the discrete measure, A Möbius-invariant power diagram and its applications to soap bubbles and planar Lombardi drawing, 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, Geometric clustering for the consolidation of farmland and woodland, Convergence rates for discretized Monge-Ampère equations and quantitative stability of optimal transport, Lower bounds for the number of hyperplanes separating two finite sets of points, Three-dimensional convex hull as a fruitful source of diagrams, Matching edges and faces in polygonal partitions, A convex hull algorithm for discs, and applications, Implementation of a randomized algorithm for Delaunay and regular triangulations in three dimensions, Data-driven selection of tessellation models describing polycrystalline microstructures, Worst-case demand distributions in vehicle routing, Randomized incremental construction of abstract Voronoi diagrams, Computing minimal interpolants in \(C^{1,1}(\mathbb{R}^d)\), Distributed computation of virtual coordinates for greedy routing in sensor networks, Volume approximation of smooth convex bodies by three-polytopes of restricted number of edges, Generalised primal-dual grids for unstructured co-volume schemes, General-dimensional constrained Delaunay and constrained regular triangulations. I: Combinatorial properties, Volume approximations of strongly pseudoconvex domains, On the estimation of the medial axis and inner parallel body, A comparative study of interface reconstruction methods for multi-material ALE simulations, Generation of statistically representative microstructures with direct grain geometry control, A team-based deployment approach for heterogeneous mobile sensor networks, Categorization generated by extended prototypes -- an axiomatic approach, Mathematical analysis and calculation of molecular surfaces, Fully Inverse Parametric Linear/Quadratic Programming Problems via Convex Liftings, A second-order accurate material-order-independent interface reconstruction technique for multi-material flow simulations, Finding an Euclidean anti-\(k\)-centrum location of a set of points, Construction of Voronoi diagrams in the plane by using maps, Laguerre Voronoi diagram as a model for generating the tessellation patterns on the sphere, An acyclicity theorem for cell complexes in d dimensions, On the construction of abstract Voronoi diagrams, The error of polytopal approximation with respect to the symmetric difference metric and the \(L_p\) metric, Approximation of smooth convex bodies by circumscribed polytopes with respect to the surface area, Delaunay simplices in diagonally distorted lattices, Robot motion planning and the single cell problem in arrangements, Poisson-Delaunay mosaics of order \(k\), The predicates of the Apollonius diagram: algorithmic analysis and implementation, Boat-sail Voronoi diagram and its computation based on a cone-approximation scheme, On the complexity of a single cell in certain arrangements of surfaces related to motion planning, Improving continuity of Voronoi-based interpolation over Delaunay spheres, On the complexity of randomly weighted multiplicative Voronoi diagrams, Finding extreme points in three dimensions and solving the post-office problem in the plane, On optimal bridges between two convex regions, Generalized Dirichlet tesselations, The one-dimensional weighted Voronoi diagram, Dynamic maintenance and visualization of molecular surfaces.
