The upper envelope of piecewise linear functions: Algorithms and applications
From MaRDI portal
Publication:919830
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
visibilitycomputational geometrycombinatorial complexityVoronoi diagramshidden line removalsurface removal
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
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
