An optimal algorithm for intersecting line segments in the plane
From MaRDI portal
Publication:4302817
DOI10.1145/147508.147511zbMath0799.68191OpenAlexW2015696135WikidataQ60017375 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
computer graphicscomputational geometryline arrangementsclippingwindowinggeometrical computationshidden- surface removal
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
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
