New bounds for lower envelopes in three dimensions, with applications to visibility in terrains

DOI10.1007/BF02574383zbMath0819.68136OpenAlexW2027982698MaRDI QIDQ1338959

Micha Sharir, Dan Halperin

Publication date: 27 August 1995

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

Full work available at URL: https://eudml.org/doc/131334

zbMATH Keywords

combinatorial complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Computing the geodesic centers of a polygonal domain, On the number of views of polyhedral terrains, On lines missing polyhedral sets in 3-space, Almost tight upper bounds for lower envelopes in higher dimensions, Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications, Unreliable point facility location problems on networks, Almost tight upper bounds for the single cell and zone problems in the three dimensions, On topological changes in the Delaunay triangulation of moving points, The overlay of lower envelopes and its applications, On-line construction of the upper envelope of triangles and surface patches in three dimensions, On the complexity of sets of free lines and line segments among balls in three dimensions, On Kinetic Delaunay Triangulations, Efficient randomized algorithms for some geometric optimization problems, A new technique for analyzing substructures in arrangements of piecewise linear surfaces, Notes on the complexity of exact view graph algorithms for piecewise smooth algebraic surfaces

Cites Work

• Unnamed Item
• The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
• Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
• Combinatorial complexity bounds for arrangements of curves and spheres
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• A singly exponential stratification scheme for real semi-algebraic varieties and its applications
• On \(k\)-sets in arrangements of curves and surfaces
• Almost tight upper bounds for lower envelopes in higher dimensions
• Applications of random sampling in computational geometry. II
• On the two-dimensional Davenport-Schinzel problem
• Schubert Calculus