On the complexity of d-dimensional Voronoi diagrams

DOI10.1007/BF01224932zbMath0414.52004OpenAlexW2332151900MaRDI QIDQ599355

Victor Klee

Publication date: 1980

Published in: Archiv der Mathematik (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01224932

zbMATH Keywords

complexityconvex polytopepolyhedronVoronoi diagramfacetvertexpolarneighborly

Mathematics Subject Classification ID

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

Related Items

Tetrahedrizing point sets in three dimensions, Representing stereo data with the Delaunay triangulation, Illuminating high-dimensional convex sets, The impact of heterogeneity and geometry on the proof complexity of random satisfiability, The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs, A new approach to output-sensitive construction of Voronoi diagrams and Delaunay triangulations, Stratifying High-Dimensional Data Based on Proximity to the Convex Hull Boundary, On the randomized construction of the Delaunay tree, Delaunay partitions in \(\mathbb R^n\) applied to non-convex programs and vertex/facet enumeration problems, Kernel interpolation, Unnamed Item, Simplex based space filling designs, An approximate algorithm for computing multidimensional convex hulls, On Some Proximity Problems of Colored Sets, Voronoi Diagrams of Moving Points, Arbitrarily large neighborly families of symmetric convex polytopes

Cites Work

• Unnamed Item
• Unnamed Item
• Polytope pairs and their relationship to linear programming
• Some semicontinuity theorems for convex polytopes and cell-complexes
• The maximum numbers of faces of a convex polytope
• The complexity of linear programming