The upper envelope of piecewise linear functions: Algorithms and applications

DOI10.1007/BF02187733zbMath0707.68044MaRDI QIDQ919830

Leonidas J. Guibas, Herbert Edelsbrunner, Micha Sharir

Publication date: 1989

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

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

zbMATH Keywords

visibilitycomputational geometrycombinatorial complexityVoronoi diagramshidden line removalsurface removal

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (35)

Optimizing resource speed for two-stage real-time tasks ⋮ Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts ⋮ Orthogonal weightet linear \(L_ 1\) and \(L_ \infty\) approximation and applications ⋮ The L∞ Hausdorff Voronoi Diagram Revisited ⋮ Triangles in space or building (and analyzing) castles in the air ⋮ The overlay of lower envelopes and its applications ⋮ On-line construction of the upper envelope of triangles and surface patches in three dimensions ⋮ Efficient view point selection for silhouettes of convex polyhedra ⋮ Remarks on the computation of the horizon of a digital terrain ⋮ Algorithms for high dimensional stabbing problems ⋮ The upper envelope of piecewise linear functions: Tight bounds on the number of faces ⋮ Voronoi diagram with visual restriction ⋮ Parameterized matching with mismatches ⋮ Computing the map of geometric minimal cuts ⋮ On \(k\)-sets in arrangements of curves and surfaces ⋮ Linear approximation of simple objects ⋮ Stabbing circles for sets of segments in the plane ⋮ THE HAUSDORFF VORONOI DIAGRAM OF POLYGONAL OBJECTS: A DIVIDE AND CONQUER APPROACH ⋮ Quasi-optimal upper bounds for simplex range searching and new zone theorems ⋮ Computing the \(L_1\) geodesic diameter and center of a polygonal domain ⋮ The upper envelope of Voronoi surfaces and its applications ⋮ Stabbers of line segments in the plane ⋮ The existence of horizontal envelopes in the 3D-Heisenberg group ⋮ Unnamed Item ⋮ A randomized incremental algorithm for the Hausdorff Voronoi diagram of non-crossing clusters ⋮ Linear approximation of simple objects ⋮ CONSTRUCTING OPTIMAL HIGHWAYS ⋮ Generalizing Geometric Graphs ⋮ Computing a minimum-width cubic and hypercubic shell ⋮ Kinetic maintenance of mobile \(k\)-centres on trees ⋮ Facility location problems in the plane based on reverse nearest neighbor queries ⋮ Optimal computation of the Voronoi diagram of disjoint clusters ⋮ The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis ⋮ Randomized incremental construction for the Hausdorff Voronoi diagram revisited and extended ⋮ An Output-Sensitive Convex Hull Algorithm for Planar Objects

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
• The upper envelope of piecewise linear functions: Tight bounds on the number of faces
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
• Computing convolutions by reciprocal search
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Planar realizations of nonlinear Davenport-Schinzel sequences by segments
• Separating two simple polygons by a sequence of translations
• Stabbing line segments
• On the general motion-planning problem with two degrees of freedom
• Triangles in space or building (and analyzing) castles in the air
• Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures
• An efficient algorithm for a complete link method
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: The upper envelope of piecewise linear functions: Algorithms and applications