A lower bound on Voronoi diagram complexity.

DOI10.1016/S0020-0190(01)00336-2zbMath1044.68855OpenAlexW1982041519MaRDI QIDQ1853066

Boris Aronov

Publication date: 21 January 2003

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(01)00336-2

zbMATH Keywords

Computational geometryVoronoi diagramComputational complexity

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Voronoi diagrams of moving points in the plane and of lines in space: tight bounds for simple configurations, A pruning algorithm for stable Voronoi skeletons, Voronoi diagrams of algebraic varieties under polyhedral norms, Voronoi Diagrams for Parallel Halflines and Line Segments in Space

Uses Software

• Voronoi

Cites Work

• Voronoi diagrams and arrangements
• Almost tight upper bounds for lower envelopes in higher dimensions
• Voronoi diagrams in higher dimensions under certain polyhedral distance functions
• A new technique for analyzing substructures in arrangements of piecewise linear surfaces
• Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions
• Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item