Topology-Oriented Incremental Algorithm for the Robust Construction of the Voronoi Diagrams of Disks

DOI10.1145/2939366zbMath1369.65032OpenAlexW2508687449WikidataQ113310159 ScholiaQ113310159MaRDI QIDQ5270775

Mokwon Lee, Deok-Soo Kim, Kōkichi Sugihara

Publication date: 30 June 2017

Published in: ACM Transactions on Mathematical Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2939366

zbMATH Keywords

simplicial complextopologysimplexdisksbeta-complexquasi-triangulationadditively-weighted Voronoi diagram

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items (4)

A parallel algorithm for computing Voronoi diagram of a set of circles using touching disc and topology matching ⋮ A dynamic sampling approach towards computing Voronoi diagram of a set of circles ⋮ QuickhullDisk: a faster convex hull algorithm for disks ⋮ Near optimal minimal convex hulls of disks

Uses Software

• CGAL
• LEDA
• VRONI
• packomania
• CAVER
• BetaSCPWeb
• BetaVoid
• BetaConcept
• QTFier

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Iterated tabu search and variable neighborhood descent for packing unequal circles into a circular container
• A sweepline algorithm for Euclidean Voronoi diagram of circles
• Topology-oriented incremental computation of Voronoi diagrams of circular arcs and straight-line segments
• Quasi-worlds and quasi-operators on quasi-triangulations
• Towards exact geometric computation
• How to simulate billiards and similar systems
• A geometric consistency theorem for a symbolic perturbation scheme
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• A sweepline algorithm for Voronoi diagrams
• On the computational geometry of pocket machining
• Swap conditions for dynamic Voronoi diagrams for circles and line segments
• Disk packing for the estimation of the size of a wire bundle
• Representing the Voronoï diagram of a simple polygon using rational quadratic Bézier curves
• Geometric properties of random disk packings.
• Updating the topology of the dynamic Voronoi diagram for spheres in Euclidean \(d\)-dimensional space
• The predicates of the Apollonius diagram: algorithmic analysis and implementation
• Qualitative Symbolic Perturbation
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• Intersection and Closest-Pair Problems for a Set of Planar Discs
• Generalization of Voronoi Diagrams in the Plane
• A ROBUST TOPOLOGY-ORIENTED INCREMENTAL ALGORITHM FOR VORONOI DIAGRAMS
• Transformation of a Dynamic B-spline Curve Into Piecewise Power Basis Representation
• On the design of CGAL a computational geometry algorithms library
• Voronoi diagram of a circle set from Voronoi diagram of a point set: I. Topology
• Voronoi diagram of a circle set from Voronoi diagram of a point set: II. Geometry
• VRONI: An engineering approach to the reliable and efficient computation of Voronoi diagrams of points and line segments

This page was built for publication: Topology-Oriented Incremental Algorithm for the Robust Construction of the Voronoi Diagrams of Disks