The overlay of lower envelopes and its applications
From MaRDI portal
Publication:1907607
DOI10.1007/BF02716576zbMath0840.68115MaRDI QIDQ1907607
Pankaj K. Agarwal, Otfried Schwarzkopf, Micha Sharir
Publication date: 27 June 1996
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (23)
Almost tight upper bounds for lower envelopes in higher dimensions ⋮ Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications ⋮ On topological changes in the Delaunay triangulation of moving points ⋮ New approaches to the robust 1-center location problems on tree networks ⋮ Arrangements on parametric surfaces. II: Concretizations and applications ⋮ On the union of cylinders in three dimensions ⋮ Shortest paths in time-dependent FIFO networks ⋮ Survivable minimum bottleneck networks ⋮ Lines avoiding balls in three dimensions revisited ⋮ Linear approximation of simple objects ⋮ On the number of views of translates of a cube and related problems. ⋮ Characterization and computation of feasible trajectories for an articulated probe with a variable-length end segment ⋮ Voronoi diagrams with respect to criteria on vision information ⋮ Locating an obnoxious plane ⋮ On Kinetic Delaunay Triangulations ⋮ Maintaining the extent of a moving point set ⋮ On overlays and minimization diagrams ⋮ A near-linear algorithm for the planar segment-center problem ⋮ A new technique for analyzing substructures in arrangements of piecewise linear surfaces ⋮ Spheres, molecules, and hidden surface removal ⋮ Facility location problems in the plane based on reverse nearest neighbor queries ⋮ Weighted Voronoi Diagrams in the Maximum Norm ⋮ Geometric optimization and sums of algebraic functions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- Combinatorial complexity bounds for arrangements of curves and spheres
- The upper envelope of piecewise linear functions: Algorithms and applications
- Some dynamic computational geometry problems
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- On \(k\)-sets in arrangements of curves and surfaces
- Common tangents and common transversals
- On the number of views of polyhedral terrains
- New bounds for lower envelopes in three dimensions, with applications to visibility in terrains
- Almost tight upper bounds for lower envelopes in higher dimensions
- Applications of random sampling in computational geometry. II
- Bounding the number of geometric permutations induced by \(k\)-transversals
- On lazy randomized incremental construction
This page was built for publication: The overlay of lower envelopes and its applications
