Power Diagrams: Properties, Algorithms and Applications
From MaRDI portal
Publication:4725255
DOI10.1137/0216006zbMath0616.52007MaRDI 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 diagram; convex hull; Voronoi diagram; efficient algorithm; Laguerre metric; concrete complexity; Dirichlet cell
Related Items
Asymptotic approximation of smooth convex bodies by general polytopes, MULTIPLE PARAMETER CONTINUATION: COMPUTING IMPLICITLY DEFINED k-MANIFOLDS, ON DELETION IN DELAUNAY TRIANGULATIONS, EUCLIDEAN VORONOI DIAGRAM FOR CIRCLES IN A CIRCLE, Regular triangulations and Steiner points, A new duality result concerning Voronoi diagrams, An efficient algorithm for the three-dimensional diameter problem, Weighted \({\mathcal A}\)-shape: A descriptor of the shape of a point set, Bregman Voronoi diagrams, Perturbations for Delaunay and weighted Delaunay 3D triangulations, Implementation of a randomized algorithm for Delaunay and regular triangulations in three dimensions, Randomized incremental construction of abstract Voronoi diagrams, Finding an Euclidean anti-\(k\)-centrum location of a set of points, Construction of Voronoi diagrams in the plane by using maps, An acyclicity theorem for cell complexes in d dimensions, On the construction of abstract Voronoi diagrams, Stable marker-particle method for the Voronoi diagram in a flow field, A relationship between Gale transforms and Voronoi diagrams, Categorization generated by extended prototypes -- an axiomatic approach, 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, 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, Three-dimensional convex hull as a fruitful source of diagrams, A comparative study of interface reconstruction methods for multi-material ALE simulations, 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, Matching edges and faces in polygonal partitions, 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, An efficient algorithm for construction of the power diagram from the voronoi diagram in the plane, Fitting three-dimensional Laguerre tessellations to foam structures, 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
