A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D

DOI10.1145/380752.380815zbMath1323.68299OpenAlexW2094748973MaRDI QIDQ5175985

Lihong Ha, Christian Icking

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

complexityconvex polytopepolyhedronbisectorVoronoi diagramconvex distance functionlower envelope

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Skew Jensen-Bregman Voronoi Diagrams

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

This page was built for publication: A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D