The upper envelope of piecewise linear functions: Algorithms and applications
From MaRDI portal
Publication:919830
DOI10.1007/BF02187733zbMath0707.68044MaRDI QIDQ919830
Herbert Edelsbrunner, Micha Sharir, Leonidas J. Guibas
Publication date: 1989
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131082
visibility; computational geometry; combinatorial complexity; Voronoi diagrams; hidden line removal; surface removal
68Q25: Analysis of algorithms and problem complexity
05C35: Extremal problems in graph theory
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
Related Items
An Output-Sensitive Convex Hull Algorithm for Planar Objects, Linear approximation of simple objects, THE HAUSDORFF VORONOI DIAGRAM OF POLYGONAL OBJECTS: A DIVIDE AND CONQUER APPROACH, The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis, Algorithms for high dimensional stabbing problems, The upper envelope of piecewise linear functions: Tight bounds on the number of faces, Parameterized matching with mismatches, Kinetic maintenance of mobile \(k\)-centres on trees, On \(k\)-sets in arrangements of curves and surfaces, Quasi-optimal upper bounds for simplex range searching and new zone theorems, The upper envelope of Voronoi surfaces and its applications, Remarks on the computation of the horizon of a digital terrain, Optimal computation of the Voronoi diagram of disjoint clusters, The overlay of lower envelopes and its applications, On-line construction of the upper envelope of triangles and surface patches in three dimensions, Orthogonal weightet linear \(L_ 1\) and \(L_ \infty\) approximation and applications, Triangles in space or building (and analyzing) castles in the air, CONSTRUCTING OPTIMAL HIGHWAYS
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
