Finding the upper envelope of n line segments in O(n log n) time

DOI10.1016/0020-0190(89)90136-1zbMath0689.68058OpenAlexW2020590137WikidataQ29302733 ScholiaQ29302733MaRDI QIDQ582095

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

zbMATH Keywords

computational geometry Davenport-Schinzel sequence upper envelope

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99)

Related Items

Parametric matroid interdiction, Two-guarding a rectilinear polygon, Guarding a terrain by two watchtowers, Translating a regular grid over a point set, An efficient $k$ nearest neighbors searching algorithm for a query line., An FPTAS for the parametric knapsack problem, Separability of imprecise points, On the minimum-area rectangular and square annulus problem, Computing a minimum-width square or rectangular annulus with outliers, Orthogonal weightet linear $L_ 1$ and $L_ \infty$ approximation and applications, The Parametric Closure Problem, Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons, On determining optimal strategies in pursuit games in the plane, Excess in arrangements of segments, Heuristic approaches for biobjective mixed 0-1 integer linear programming problems, Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor, Connect the Dot: Computing Feed-Links with Minimum Dilation, Efficient algorithms for combined heat and power production planning under the deregulated electricity market, Undesirable facility location problems on multicriteria networks, The robust bilevel continuous knapsack problem with uncertain coefficients in the follower's objective, Vertical decompositions for triangles in 3-space, A polynomial algorithm for the multicriteria cent-dian location problem, An $O(mn)$ algorithm for the anti-cent-dian problem, Minimizing the Weighted Directed Hausdorff Distance between Colored Point Sets under Translations and Rigid Motions, Almost optimal algorithms for diameter-optimally augmenting trees, Computing depth orders for fat objects and related problems, Computing half-plane and strip discrepancy of planar point sets, Topological stability of kinetic $k$-centers, Compaction and separation algorithms for non-convex polygons and their applications, On weighting two criteria with a parameter in combinatorial optimization problems, The vehicle routing problem with arrival time diversification on a multigraph, $$\beta $$-skeletons for a Set of Line Segments in $$R^2 $$, Minimizing the weighted directed Hausdorff distance between colored point sets under translations and rigid motions, Querying two boundary points for shortest paths in a polygonal domain, Routing in a polygonal terrain with the shortest beacon watchtower, Separating bichromatic point sets by L-shapes, Continuous location of dimensional structures., Remarks on the computation of the horizon of a digital terrain, Computing a minimum-width square annulus in arbitrary orientation, Trajectory planning for an articulated probe, Empty squares in arbitrary orientation among points, Linear approximation of simple objects, CONTINUOUS PATH VERIFICATION IN MULTI-AXIS NC-MACHINING, Kinetic Maintenance of Mobile k-Centres on Trees, Finding best swap edges minimizing the routing cost of a spanning tree, Scandinavian thins on top of cake: new and improved algorithms for stacking and packing, Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights, Linear approximation of simple objects, 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, 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, THE ONION DIAGRAM: A VORONOI-LIKE TESSELLATION OF A PLANAR LINE SPACE AND ITS APPLICATIONS, Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments, Upper envelope onion peeling, Approximation algorithms for indefinite quadratic programming, An intersection model for multitolerance graphs: efficient algorithms and hierarchy, Visibility maps of segments and triangles in 3D, Capturing crossings: convex hulls of segment and plane intersections, Separating objects in the plane by wedges and strips, The multicriteria $p$-facility median location problem on networks, The upper envelope of Voronoi surfaces and its applications, Bichromatic 2-center of pairs of points, Largest empty circle centered on a query line, The existence of horizontal envelopes in the 3D-Heisenberg group, Upper envelope onion peeling, Unnamed Item, Unnamed Item, The maximum absolute deviation measure in location problems on networks, Fréchet distance between a line and avatar point set, Algorithms for covering multiple barriers, Linear approximation of simple objects, On a pair of job-machine assignment problems with two stages, Maximum-width empty square and rectangular annulus, Computing a Minimum-Width Square Annulus in Arbitrary Orientation, Almost linear time algorithms for minsum $k$-sink problems on dynamic flow path networks, COMPUTING THE SET OF ALL THE DISTANT HORIZONS OF A TERRAIN, A persistence landscapes toolbox for topological statistics, Computing a minimum-width cubic and hypercubic shell, Optimizing generalized kernels of polygons, Computing a Minimum-Width Square or Rectangular Annulus with Outliers, An algorithmic toolbox for network calculus, On determining optimal strategies in pursuit games in the plane, Optimal output-sensitive convex hull algorithms in two and three dimensions, Computing shortest transversals, Kinetic maintenance of mobile $k$-centres on trees, Covering a set of line segments with a few squares, SMALLEST COLOR-SPANNING OBJECT REVISITED, Unnamed Item, Computing the dilation of edge-augmented graphs in metric spaces, Geometric methods to solve max-ordering location problems, Minimum-width double-strip and parallelogram annulus, Faster algorithms for growing prioritized disks and rectangles, One-way and round-trip center location problems, Robot motion planning and the single cell problem in arrangements, Unnamed Item, An improved method for calculating the no-fit polygon, Optimizing airspace closure with respect to politicians' egos, On the union of fat wedges and separating a collection of segments by a line, An Output-Sensitive Convex Hull Algorithm for Planar Objects, Visibility with a moving point of view, The maximum-level vertex in an arrangement of lines

Cites Work