Finding the upper envelope of n line segments in O(n log n) time
From MaRDI portal
DOI10.1016/0020-0190(89)90136-1zbMATH Open0689.68058OpenAlexW2020590137WikidataQ29302733 ScholiaQ29302733MaRDI QIDQ582095FDOQ582095
Authors: John Hershberger 
Publication date: 1989
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(89)90136-1
Recommendations
Computing methodologies and applications (68U99) Analysis of algorithms and problem complexity (68Q25)
Cites Work
- Title not available (Why is that?)
- Finding the maximum, merging, and sorting in a parallel computation model
- Fast Algorithms for Finding Nearest Common Ancestors
- Parallel Merge Sort
- Some dynamic computational geometry problems
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- A Combinatorial Problem Connected with Differential Equations
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- Planar realizations of nonlinear Davenport-Schinzel sequences by segments
- Visibility of disjoint polygons
Cited In (only showing first 100 items - show all)
- Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor
- An efficient \(k\) nearest neighbors searching algorithm for a query line.
- Capturing crossings: convex hulls of segment and plane intersections
- On the minimum-area rectangular and square annulus problem
- Maximum-width empty square and rectangular annulus
- Bichromatic 2-center of pairs of points
- Approximating minimum-area rectangular and convex containers for packing convex polygons
- Upper envelope onion peeling
- Largest empty circle centered on a query line
- Geometric methods to solve max-ordering location problems
- Output-sensitive algorithms for optimally constructing the upper envelope of straight line segments in parallel
- 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
- Vertical decompositions for triangles in 3-space
- Approximation algorithms for indefinite quadratic programming
- 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
- Almost optimal algorithms for diameter-optimally augmenting trees
- On a pair of job-machine assignment problems with two stages
- Optimal output-sensitive convex hull algorithms in two and three dimensions
- The upper envelope of Voronoi surfaces and its applications
- The upper envelope of piecewise linear functions: Tight bounds on the number of faces
- Kinetic Maintenance of Mobile k-Centres on Trees
- An FPTAS for the parametric knapsack problem
- Heuristic approaches for biobjective mixed 0-1 integer linear programming problems
- A polynomial algorithm for the multicriteria cent-dian location problem
- Fréchet distance between a line and avatar point set
- On determining optimal strategies in pursuit games in the plane
- On the union of fat wedges and separating a collection of segments by a line
- Upper envelope onion peeling
- 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
- Continuous location of dimensional structures.
- Efficient algorithms for combined heat and power production planning under the deregulated electricity market
- An algorithmic toolbox for network calculus
- Finding best swap edges minimizing the routing cost of a spanning tree
- Separating bichromatic point sets by L-shapes
- Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments
- SMALLEST COLOR-SPANNING OBJECT REVISITED
- 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
- Minimum-width double-strip and parallelogram annulus
- On determining optimal strategies in pursuit games in the plane
- Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
- An \(O(n^2\log^2 n)\) time algorithm for minmax regret minsum sink on path networks
- An Output-Sensitive Convex Hull Algorithm for Planar Objects
- Querying two boundary points for shortest paths in a polygonal domain
- Robot motion planning and the single cell problem in arrangements
- Covering a set of line segments with a few squares
- Computing the dilation of edge-augmented graphs in metric spaces
- Separability of imprecise points
- The maximum absolute deviation measure in location problems on networks
- Topological stability of kinetic \(k\)-centers
- Computing a minimum-width square annulus in arbitrary orientation
- The multicriteria \(p\)-facility median location problem on networks
- Shortest rectilinear path queries to rectangles in a rectangular domain
- Characterization and computation of feasible trajectories for an articulated probe with a variable-length end segment
- Linear approximation of simple objects
- Faster algorithms for growing prioritized disks and rectangles
- Trajectory planning for an articulated probe
- \(\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
- The existence of horizontal envelopes in the 3D-Heisenberg group
- Minimizing the Weighted Directed Hausdorff Distance between Colored Point Sets under Translations and Rigid Motions
- Optimizing airspace closure with respect to politicians' egos
- Sink location problems in dynamic flow grid networks
- Empty squares in arbitrary orientation among points
- Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights
- An intersection model for multitolerance graphs: efficient algorithms and hierarchy
- Title not available (Why is that?)
- The vehicle routing problem with arrival time diversification on a multigraph
- CONTINUOUS PATH VERIFICATION IN MULTI-AXIS NC-MACHINING
- Routing in a polygonal terrain with the shortest beacon watchtower
- 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
- Computing a Minimum-Width Square Annulus in Arbitrary Orientation
- Computing a Minimum-Width Square or Rectangular Annulus with Outliers
- Sink location problems in dynamic flow grid networks
- Optimizing generalized kernels of polygons
- Title not available (Why is that?)
- Guarding a terrain by two watchtowers
- Almost linear time algorithms for minsum \(k\)-sink problems on dynamic flow path networks
- Visibility maps of segments and triangles in 3D
- COMPUTING THE SET OF ALL THE DISTANT HORIZONS OF A TERRAIN
- An improved method for calculating the no-fit polygon
- Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights
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)
