On overlays and minimization diagrams

DOI10.1007/s00454-009-9139-5zbMath1455.52027OpenAlexW2005644466MaRDI QIDQ1014331

Micha Sharir, Vladlen Koltun

Publication date: 27 April 2009

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-009-9139-5

zbMATH Keywords

arrangementscombinatorial complexityoverlayslower envelopesminimization diagrams

Mathematics Subject Classification ID

Combinatorial complexity of geometric structures (52C45)

Related Items (2)

Maximal f-vectors of Minkowski sums of large numbers of polytopes ⋮ Geometric optimization and sums of algebraic functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The upper envelope of piecewise linear functions: Tight bounds on the number of faces
• Voronoi diagrams and arrangements
• An optimal convex hull algorithm in any fixed dimension
• Almost tight upper bounds for lower envelopes in higher dimensions
• Approximation algorithms for minimum-width annuli and shells
• Matching polyhedral terrains using overlays of envelopes
• Vertical decomposition of arrangements of hyperplanes in four dimensions
• The overlay of lower envelopes and its applications
• A Randomized Algorithm for Closest-Point Queries
• Lectures on Polytopes
• Computing Envelopes in Four Dimensions with Applications
• The Partition Technique for Overlays of Envelopes
• APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
• The maximum numbers of faces of a convex polytope
• Algorithms in real algebraic geometry
• Exact and approximation algorithms for minimum-width cylindrical shells

This page was built for publication: On overlays and minimization diagrams