Improved algorithms for discs and balls using power diagrams

DOI10.1016/0196-6774(88)90035-1zbMath0642.52009OpenAlexW1982777080MaRDI QIDQ3784733

Franz Aurenhammer

Publication date: 1988

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(88)90035-1

zbMATH Keywords

power diagramVoronoi diagramcomputational geometryunion and intersection of discs and balls

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Artificial intelligence (68T99) Other problems of combinatorial convexity (52A37) Polytopes and polyhedra (52Bxx)

Related Items

Local calculation of Voronoi diagrams, The union of balls and its dual shape, 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects, A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM, Computing constrained minimum-width annuli of point sets, Dot to dot, simple or sophisticated: a survey on shape reconstruction algorithms, Asymmetric tropical distances and power diagrams, Constructing the relative neighborhood graph in 3-dimensional Euclidean space, Farthest neighbors, maximum spanning trees and related problems in higher dimensions, An efficient algorithm for the three-dimensional diameter problem, Unnamed Item, On the construction of abstract Voronoi diagrams, MULTIPLE PARAMETER CONTINUATION: COMPUTING IMPLICITLY DEFINED k-MANIFOLDS, TERRAIN VISIBILITY WITH MULTIPLE VIEWPOINTS, An armature structure for 3D shapes