Almost tight upper bounds for lower envelopes in higher dimensions
From MaRDI portal
Publication:1338960
DOI10.1007/BF02574384zbMath0819.68068OpenAlexW2011387411MaRDI QIDQ1338960
Publication date: 27 August 1995
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131335
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Extremal combinatorics (05D99)
Related Items (35)
Anisotropic sources for surface and volume boundary layer mesh generation ⋮ Computing the geodesic centers of a polygonal domain ⋮ New bounds for lower envelopes in three dimensions, with applications to visibility in terrains ⋮ The Offset Filtration of Convex Objects ⋮ Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications ⋮ Unreliable point facility location problems on networks ⋮ Straight skeletons and mitered offsets of nonconvex polytopes ⋮ Almost tight upper bounds for the single cell and zone problems in the three dimensions ⋮ The overlay of lower envelopes and its applications ⋮ Vertical decompositions for triangles in 3-space ⋮ On-line construction of the upper envelope of triangles and surface patches in three dimensions ⋮ Querying two boundary points for shortest paths in a polygonal domain ⋮ Voronoi Diagram of Polygonal Chains under the Discrete Fréchet Distance ⋮ Casting a polyhedron with directional uncertainty ⋮ Faster algorithms for largest empty rectangles and boxes ⋮ Survivable minimum bottleneck networks ⋮ Linear approximation of simple objects ⋮ Straight Skeletons of Three-Dimensional Polyhedra ⋮ The multicriteria \(p\)-facility median location problem on networks ⋮ VORONOI DIAGRAM OF POLYGONAL CHAINS UNDER THE DISCRETE FRÉCHET DISTANCE ⋮ On Kinetic Delaunay Triangulations ⋮ COMPUTING THE SET OF ALL THE DISTANT HORIZONS OF A TERRAIN ⋮ Unnamed Item ⋮ On overlays and minimization diagrams ⋮ On determining optimal strategies in pursuit games in the plane ⋮ A near-linear algorithm for the planar segment-center problem ⋮ Efficient randomized algorithms for some geometric optimization problems ⋮ A new technique for analyzing substructures in arrangements of piecewise linear surfaces ⋮ The Voronoi diagram of three lines ⋮ Weighted Voronoi Diagrams in the Maximum Norm ⋮ The geometry of Minkowski spaces -- a survey. II. ⋮ A lower bound on Voronoi diagram complexity. ⋮ Voronoi Diagrams for Parallel Halflines and Line Segments in Space ⋮ On the complexity of randomly weighted multiplicative Voronoi diagrams ⋮ Optimal partitioning for spatiotemporal coverage in a drift field
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Diameter, width, closest line pair, and parametric searching
- 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
- Voronoi diagrams and arrangements
- \(\epsilon\)-nets and simplex range queries
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- On \(k\)-sets in arrangements of curves and surfaces
- New bounds for lower envelopes in three dimensions, with applications to visibility in terrains
- New applications of random sampling in computational geometry
- Applications of random sampling in computational geometry. II
- The overlay of lower envelopes and its applications
- Lines in space: Combinatorics and algorithms
- On-line construction of the upper envelope of triangles and surface patches in three dimensions
- On the two-dimensional Davenport-Schinzel problem
- VORONOI DIAGRAMS OF MOVING POINTS IN THE PLANE
- Ray Shooting Amidst Spheres in Three Dimensions and Related Problems
- Computing Envelopes in Four Dimensions with Applications
- On lazy randomized incremental construction
This page was built for publication: Almost tight upper bounds for lower envelopes in higher dimensions
