The upper envelope of piecewise linear functions: Algorithms and applications
From MaRDI portal
This article is devoted to the combinatorial complexity of the upper envelope of piecewise linear functions and its consequences to various problems in computational geometry. The upper envelope of the system of functions is defined as its pointwise maximum. In the case of linear functions the envelope form a cell complex. The complexity of the complex is the number of its faces. An algorithm is presented for finding the upper envelope of n linear functions defined in the space \(R^ 3\). The algorithm is asymptotically optimal and its time complexity is \(O(n^ 2\alpha (n))\) where \(\alpha\) (n) is the inverse of Ackermann's function. Finding an upper envelope for appropriate system of linear functions solves a number of problems of computational geometry. Among the applications are mentioned problems of hidden line and surface removal, translating a polyhedron in the space with polyhedral obstacles, finding Voronoi diagrams of point clusters.
Recommendations
- The upper envelope of piecewise linear functions: Tight bounds on the number of faces
- The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
- Finding the upper envelope of n line segments in O(n log n) time
- Almost tight upper bounds for lower envelopes in higher dimensions
- The overlay of lower envelopes and its applications
Cites work
- An efficient algorithm for a complete link method
- Computing convolutions by reciprocal search
- Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
- Depth-First Search and Linear Graph Algorithms
- scientific article; zbMATH DE number 3945379 (Why is no real title available?)
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- scientific article; zbMATH DE number 3579840 (Why is no real title available?)
- scientific article; zbMATH DE number 3451445 (Why is no real title available?)
- Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- On the general motion-planning problem with two degrees of freedom
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
- Planar realizations of nonlinear Davenport-Schinzel sequences by segments
- Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
- Separating two simple polygons by a sequence of translations
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
- Stabbing line segments
- 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
- Triangles in space or building (and analyzing) castles in the air
Cited in
(44)- Kinetic maintenance of mobile \(k\)-centres on trees
- Facility location problems in the plane based on reverse nearest neighbor queries
- On \(k\)-sets in arrangements of curves and surfaces
- A simple algorithm for determining the envelope of a set of lines
- 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
- Stabbing circles for sets of segments in the plane
- The overlay of lower envelopes and its applications
- On-line construction of the upper envelope of triangles and surface patches in three dimensions
- Computing a minimum-width cubic and hypercubic shell
- Optimizing resource speed for two-stage real-time tasks
- Orthogonal weightet linear \(L_ 1\) and \(L_ \infty\) approximation and applications
- Voronoi diagram with visual restriction
- Triangles in space or building (and analyzing) castles in the air
- The L∞ Hausdorff Voronoi Diagram Revisited
- CONSTRUCTING OPTIMAL HIGHWAYS
- Computing Envelopes in Four Dimensions with Applications
- An Output-Sensitive Convex Hull Algorithm for Planar Objects
- Computing the map of geometric minimal cuts
- Planar lower envelope of monotone polygonal chains
- Faster algorithms for next breakpoint and max value for parametric global minimum cuts
- scientific article; zbMATH DE number 7559380 (Why is no real title available?)
- Linear approximation of simple objects
- The existence of horizontal envelopes in the 3D-Heisenberg group
- Computing the \(L_1\) geodesic diameter and center of a polygonal domain
- Stabbers of line segments in the plane
- THE HAUSDORFF VORONOI DIAGRAM OF POLYGONAL OBJECTS: A DIVIDE AND CONQUER APPROACH
- Finding the upper envelope of n line segments in O(n log n) time
- Generalizing geometric graphs
- Linear approximation of simple objects
- Randomized incremental construction for the Hausdorff Voronoi diagram revisited and extended
- Efficient view point selection for silhouettes of convex polyhedra
- Optimization of battery management in telecommunications networks under energy market incentives
- Unbounded regions of high-order Voronoi diagrams of lines and line segments in higher dimensions
- The farthest color Voronoi diagram in the plane
- Minimum-width double-slabs and widest empty slabs in high dimensions
- Largest convex hulls for convex-hull disjoint clusters with bounded size
- Higher-order color Voronoi diagrams and the colorful Clarkson-Shor framework
- 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
This page was built for publication: The upper envelope of piecewise linear functions: Algorithms and applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q919830)
