Finding the upper envelope of n line segments in O(n log n) time
From MaRDI portal
(Redirected from Publication:582095)
Recommendations
Cites work
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- A Combinatorial Problem Connected with Differential Equations
- Fast Algorithms for Finding Nearest Common Ancestors
- Finding the maximum, merging, and sorting in a parallel computation model
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- Parallel Merge Sort
- Planar realizations of nonlinear Davenport-Schinzel sequences by segments
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- Some dynamic computational geometry problems
- Visibility of disjoint polygons
Cited in
(only showing first 100 items - show all)- Linear approximation of simple objects
- Separability of imprecise points
- Covering a set of line segments with a few squares
- Computing a minimum-width square annulus in arbitrary orientation
- Topological stability of kinetic \(k\)-centers
- The multicriteria \(p\)-facility median location problem on networks
- The maximum absolute deviation measure in location problems on networks
- Parametric matroid interdiction
- The rectilinear convex hull of line segments
- Linear approximation of simple objects
- Characterization and computation of feasible trajectories for an articulated probe with a variable-length end segment
- Shortest rectilinear path queries to rectangles in a rectangular domain
- Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor
- Capturing crossings: convex hulls of segment and plane intersections
- An efficient \(k\) nearest neighbors searching algorithm for a query line.
- On the minimum-area rectangular and square annulus problem
- Faster algorithms for growing prioritized disks and rectangles
- Trajectory planning for an articulated probe
- Bichromatic 2-center of pairs of points
- Linear approximation of simple objects
- Upper envelope onion peeling
- Approximating minimum-area rectangular and convex containers for packing convex polygons
- Maximum-width empty square and rectangular annulus
- Largest empty circle centered on a query line
- Geometric methods to solve max-ordering location problems
- \(\beta\)-skeletons for a set of line segments in \(\mathbb R^2\)
- Remarks on the computation of the horizon of a digital terrain
- The maximum-level vertex in an arrangement of lines
- Output-sensitive algorithms for optimally constructing the upper envelope of straight line segments in parallel
- The existence of horizontal envelopes in the 3D-Heisenberg group
- Orthogonal weightet linear \(L_ 1\) and \(L_ \infty\) approximation and applications
- Compaction and separation algorithms for non-convex polygons and their applications
- Computing a minimum-width square or rectangular annulus with outliers
- Undesirable facility location problems on multicriteria networks
- Optimizing airspace closure with respect to politicians' egos
- Minimizing the Weighted Directed Hausdorff Distance between Colored Point Sets under Translations and Rigid Motions
- Empty squares in arbitrary orientation among points
- Sink location problems in dynamic flow grid networks
- Approximation algorithms for indefinite quadratic programming
- Vertical decompositions for triangles in 3-space
- Computing depth orders for fat objects and related problems
- An \(O(mn)\) algorithm for the anti-cent-dian problem
- Separating objects in the plane by wedges and strips
- Translating a regular grid over a point set
- Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights
- On a pair of job-machine assignment problems with two stages
- Almost optimal algorithms for diameter-optimally augmenting trees
- An intersection model for multitolerance graphs: efficient algorithms and hierarchy
- Optimal output-sensitive convex hull algorithms in two and three dimensions
- The upper envelope of piecewise linear functions: Tight bounds on the number of faces
- The upper envelope of Voronoi surfaces and its applications
- scientific article; zbMATH DE number 2081104 (Why is no real title available?)
- An FPTAS for the parametric knapsack problem
- Heuristic approaches for biobjective mixed 0-1 integer linear programming problems
- Kinetic Maintenance of Mobile k-Centres on Trees
- A polynomial algorithm for the multicriteria cent-dian location problem
- The vehicle routing problem with arrival time diversification on a multigraph
- Fréchet distance between a line and avatar point set
- Routing in a polygonal terrain with the shortest beacon watchtower
- CONTINUOUS PATH VERIFICATION IN MULTI-AXIS NC-MACHINING
- Two-guarding a rectilinear polygon
- Computing half-plane and strip discrepancy of planar point sets
- The robust bilevel continuous knapsack problem with uncertain coefficients in the follower's objective
- On determining optimal strategies in pursuit games in the plane
- Computing a Minimum-Width Square Annulus in Arbitrary Orientation
- Computing a Minimum-Width Square or Rectangular Annulus with Outliers
- On the union of fat wedges and separating a collection of segments by a line
- Visibility with a moving point of view
- Minimizing the weighted directed Hausdorff distance between colored point sets under translations and rigid motions
- Computing shortest transversals
- Kinetic maintenance of mobile \(k\)-centres on trees
- Upper envelope onion peeling
- Continuous location of dimensional structures.
- Efficient algorithms for combined heat and power production planning under the deregulated electricity market
- Optimizing generalized kernels of polygons
- An algorithmic toolbox for network calculus
- Sink location problems in dynamic flow grid networks
- Finding best swap edges minimizing the routing cost of a spanning tree
- scientific article; zbMATH DE number 7278008 (Why is no real title available?)
- Separating bichromatic point sets by L-shapes
- Guarding a terrain by two watchtowers
- Visibility maps of segments and triangles in 3D
- Almost linear time algorithms for minsum \(k\)-sink problems on dynamic flow path networks
- Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments
- COMPUTING THE SET OF ALL THE DISTANT HORIZONS OF A TERRAIN
- SMALLEST COLOR-SPANNING OBJECT REVISITED
- An improved method for calculating the no-fit polygon
- One-way and round-trip center location problems
- On weighting two criteria with a parameter in combinatorial optimization problems
- The upper envelope of piecewise linear functions: Algorithms and applications
- A persistence landscapes toolbox for topological statistics
- Scandinavian thins on top of cake: new and improved algorithms for stacking and packing
- Fast algorithm for partial covers in words
- Planar lower envelope of monotone polygonal chains
- Minmax regret 1-center algorithms for path/tree/unicycle/cactus networks
- Computing a minimum-width cubic and hypercubic shell
- Minimum-width double-strip and parallelogram annulus
- Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights
- On determining optimal strategies in pursuit games in the plane
- Excess in arrangements of segments
This page was built for publication: Finding the upper envelope of n line segments in O(n log n) time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q582095)
