An optimal algorithm for constructing the weighted Voronoi diagram in the plane

DOI10.1016/0031-3203(84)90064-5zbMATH Open0539.52008OpenAlexW2001099600MaRDI QIDQ793982FDOQ793982

Franz Aurenhammer, Herbert Edelsbrunner

Publication date: 1984

Published in: Pattern Recognition (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0031-3203(84)90064-5

zbMATH Keywords

domain of influenceweighted pointsgeometric transformball(p,q)circ(p,q)

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A New Approach to Planar Point Location
• Construction of Voronoi polyhedra
• The one-dimensional weighted Voronoi diagram

Cited In (62)

• An analytical representation of the 2d generalized balanced power diagram
• The impact of heterogeneity and geometry on the proof complexity of random satisfiability
• The optimal algorithm for dynamic support of the Voronoi Diagram for a set of points
• THE ONION DIAGRAM: A VORONOI-LIKE TESSELLATION OF A PLANAR LINE SPACE AND ITS APPLICATIONS
• Connecting Red Cells in a Bicolour Voronoi Diagram
• Linear expected complexity for directional and multiplicative Voronoi diagrams
• Sensitivity analysis and tailored design of minimization diagrams
• A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM
• On bisectors for different distance functions
• Dynamic weighted Voronoi diagrams and weighted minimax matching of two corresponding point sets
• MULTIPLE PARAMETER CONTINUATION: COMPUTING IMPLICITLY DEFINED k-MANIFOLDS
• Competitive spatial models
• Boat-sail Voronoi diagram and its computation based on a cone-approximation scheme
• OPTIMAL FACILITY LOCATION UNDER VARIOUS DISTANCE FUNCTIONS
• Planar expropriation problem with non-rigid rectangular facilities
• Order-k Voronoi diagrams of sites with additive weights in the plane
• Farthest line segment Voronoi diagrams
• On the geodesic Voronoi diagram of point sites in a simple polygon
• Tailoring unstructured meshes for use with a 3D time domain co-volume algorithm for computational electromagnetics
• Minimizing the Weighted Directed Hausdorff Distance between Colored Point Sets under Translations and Rigid Motions
• Voronoi diagrams and arrangements
• Weighted Voronoi region algorithms for political districting
• Finding constrained and weighted Voronoi diagrams in the plane
• The weighted farthest color Voronoi diagram on trees and graphs.
• A surface remeshing approach
• Voronoi diagrams with overlapping regions
• Large-nconditional facednessm_nof 3D Poisson–Voronoi cells
• Stable marker-particle method for the Voronoi diagram in a flow field
• Solving the \(k\)-influence region problem with the GPU
• Title not available (Why is that?)
• On the construction of abstract Voronoi diagrams
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• A sweepline algorithm for Voronoi diagrams
• Fast and efficient computation of additively weighted Voronoi cells for applications in molecular biology
• Batched Point Location in SINR Diagrams via Algebraic Tools
• An \(O(mn^ 2)\) algorithm for the maximin problem in \(E^ 2\)
• Fast Voronoi modeling
• Theory of continuous optimal set partitioning problems as a universal mathematical formalism for constructing Voronoi diagrams and their generalizations. II: Algorithms for constructing Voronoi diagrams based on the theory of optimal set partitioning
• Kinetic collision detection for convex fat objects
• Voronoi diagrams over dynamic scenes
• Voronoi diagram with visual restriction
• Abstract Voronoi Diagrams from Closed Bisecting Curves
• Minimizing the weighted directed Hausdorff distance between colored point sets under translations and rigid motions
• Weighted Voronoi Diagrams in the Maximum Norm
• A workbench for computational geometry
• BOAT-SAIL VORONOI DIAGRAM AND ITS APPLICATION
• Optimal evasive strategies for multiple interacting agents with motion constraints
• Political districting: From classical models to recent approaches
• An Efficient, Practical Algorithm and Implementation for Computing Multiplicatively Weighted Voronoi Diagrams
• Nonuniform SINR+Voronoi diagrams are effectively uniform
• Political districting: from classical models to recent approaches
• Coresets for the Nearest-Neighbor Rule
• On determining optimal strategies in pursuit games in the plane
• On the circles of Apollonius associated with a triangle
• Fuzzy Voronoi Diagram
• Generalized Voronoi tessellation as a model of two-dimensional cell tissue dynamics
• The one-dimensional weighted Voronoi diagram
• Shapes of Delaunay Simplexes and Structural Analysis of Hard Sphere Packings
• A parallel algorithm based on convexity for the computing of Delaunay tessellation
• Manifold reconstruction using tangential Delaunay complexes
• On the recognition and reconstruction of weighted Voronoi diagrams and bisector graphs
• On the complexity of randomly weighted multiplicative Voronoi diagrams

   Recommendations

• The one-dimensional weighted Voronoi diagram 👍 👎
• Order-k Voronoi diagrams of sites with additive weights in the plane 👍 👎
• Title not available (Why is that?) 👍 👎
• Voronoi diagrams and Delaunay triangulations 👍 👎
• Finding constrained and weighted Voronoi diagrams in the plane 👍 👎

This page was built for publication: An optimal algorithm for constructing the weighted Voronoi diagram in the plane

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