An optimal algorithm for intersecting line segments in the plane

DOI10.1145/147508.147511zbMath0799.68191DBLPjournals/jacm/ChazelleE92OpenAlexW2015696135WikidataQ60017375 ScholiaQ60017375MaRDI QIDQ4302817

Herbert Edelsbrunner, Bernard Chazelle

Publication date: 13 November 1994

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/147508.147511

zbMATH Keywords

computer graphicscomputational geometryline arrangementsclippingwindowinggeometrical computationshidden- surface removal

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (77)

An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments ⋮ Ray shooting on triangles in 3-space ⋮ Separability by two lines and by nearly straight polygonal chains ⋮ Efficient algorithms for counting and reporting pairwise intersections between convex polygons ⋮ Using sparsification for parametric minimum spanning tree problems ⋮ Asymptotic speed-ups in constructive solid geometry ⋮ LOCATING AN OBNOXIOUS LINE AMONG PLANAR OBJECTS ⋮ REPORTING BICHROMATIC SEGMENT INTERSECTIONS FROM POINT SETS ⋮ An introduction to randomization in computational geometry ⋮ Point probe decision trees for geometric concept classes ⋮ Filling polyhedral molds ⋮ A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums ⋮ Line-segment intersection made in-place ⋮ OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS ⋮ RED-BLUE SEPARABILITY PROBLEMS IN 3D ⋮ Sweep methods for parallel computational geometry ⋮ Vertical decompositions for triangles in 3-space ⋮ An intersection-sensitive algorithm for snap rounding ⋮ The touring rays and related problems ⋮ Randomized geometric algorithms and pseudorandom generators ⋮ Every Graph Admits an Unambiguous Bold Drawing ⋮ Untangling planar curves ⋮ Combinatorics of intervals in the plane. I: Trapezoids ⋮ Decomposable multi-parameter matroid optimization problems. ⋮ Path planning in a weighted planar subdivision under the Manhattan metric ⋮ Efficient view point selection for silhouettes of convex polyhedra ⋮ Near-linear-time deterministic plane Steiner spanners for well-spaced point sets ⋮ Geometric multicut: shortest fences for separating groups of objects in the plane ⋮ Algebraic properties of location problems with one circular barrier. ⋮ Partitioning arrangements of lines. II: Applications ⋮ Bold graph drawings ⋮ Efficient Algorithms for Touring a Sequence of Convex Polygons and Related Problems ⋮ An introduction to randomized algorithms ⋮ Packing \([1, \Delta \)-factors in graphs of small degree] ⋮ External-memory algorithms for processing line segments in geographic information systems ⋮ OVERLAYING SURFACE MESHES, PART I: ALGORITHMS ⋮ On counting pairs of intersecting segments and off-line triangle range searching ⋮ Applications of random sampling to on-line algorithms in computational geometry ⋮ New upper bounds for generalized intersection searching problems ⋮ Line-segment intersection reporting in parallel ⋮ Counting and cutting cycles of lines and rods in space ⋮ Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments ⋮ An algebraic algorithm to compute the exact general sweep boundary of a 2D curved object ⋮ Minimum-link paths among obstacles in the plane ⋮ GUARDING A POLYGON FROM TWO NEARLY-OPPOSITE DIRECTIONS ⋮ Techniques and Open Questions in Computational Convex Analysis ⋮ RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS ⋮ Unnamed Item ⋮ Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection ⋮ ON COMPUTING TRANSLATIONAL SWEPT VOLUMES ⋮ An elementary algorithm for reporting intersections of red/blue curve segments ⋮ A tail estimate for Mulmuley's segment intersection algorithm ⋮ Polyhedral circuits and their applications ⋮ Topological sweep of the complete graph ⋮ Optimal Higher Order Delaunay Triangulations of Polygons ⋮ Constructing arrangements optimally in parallel ⋮ MINIMUM SEPARATION IN WEIGHTED SUBDIVISIONS ⋮ On the general motion-planning problem with two degrees of freedom ⋮ Implicitly representing arrangements of lines or segments ⋮ Isomorphism of spiral polygons ⋮ Topologically sweeping visibility complexes via pseudotriangulations ⋮ Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle ⋮ Optimal higher order Delaunay triangulations of polygons ⋮ Applications of random sampling in computational geometry. II ⋮ Tight bounds on the solutions of multidimensional divide-and-conquer maximin recurrences ⋮ A POLYNOMIAL-TIME ALGORITHM FOR COMPUTING THE RESILIENCE OF ARRANGEMENTS OF RAY SENSORS ⋮ Complexity of projected images of convex subdivisions ⋮ Counting and representing intersections among triangles in three dimensions ⋮ Reporting intersections among thick objects. ⋮ Algorithms for bichromatic line-segment problems and polyhedral terrains ⋮ On the union of fat wedges and separating a collection of segments by a line ⋮ Reporting intersecting pairs of convex polytopes in two and three dimensions ⋮ Iterated snap rounding ⋮ Weak visibility queries of line segments in simple polygons ⋮ Rounding Arrangements Dynamically ⋮ Decision Trees for Geometric Models ⋮ The maximum-level vertex in an arrangement of lines

This page was built for publication: An optimal algorithm for intersecting line segments in the plane