An optimal algorithm for intersecting line segments in the plane
From MaRDI portal
Publication:4302817
Recommendations
Cited in
(97)- Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
- Iterated snap rounding
- Reporting intersecting pairs of convex polytopes in two and three dimensions
- Implicitly representing arrangements of lines or segments
- Optimal higher order Delaunay triangulations of polygons
- Ray shooting on triangles in 3-space
- On counting pairs of intersecting segments and off-line triangle range searching
- Algorithms and Data Structures
- On computing connected components of line segments
- Efficient algorithms for line and curve segment intersection using restricted predicates
- Decomposable multi-parameter matroid optimization problems.
- Algorithms for bichromatic line-segment problems and polyhedral terrains
- Randomized geometric algorithms and pseudorandom generators
- Vertical decompositions for triangles in 3-space
- Applications of random sampling in computational geometry. II
- On the union of fat wedges and separating a collection of segments by a line
- Optimal Higher Order Delaunay Triangulations of Polygons
- Algebraic properties of location problems with one circular barrier.
- scientific article; zbMATH DE number 4062593 (Why is no real title available?)
- An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments
- Approximation Algorithms for Hitting Triangle-Free Sets of Line Segments
- Rounding Arrangements Dynamically
- Line-segment intersection reporting in parallel
- Point probe decision trees for geometric concept classes
- Packing \([1, \Delta ]\)-factors in graphs of small degree
- Near-linear-time deterministic plane Steiner spanners for well-spaced point sets
- A tail estimate for Mulmuley's segment intersection algorithm
- GUARDING A POLYGON FROM TWO NEARLY-OPPOSITE DIRECTIONS
- An $O(E\log E + I)$ Expected Time Algorithm for the Planar Segment Intersection Problem
- An optimal algorithm for solving collision distance between convex polygons in plane
- Asymptotic speed-ups in constructive solid geometry
- Efficient algorithms for touring a sequence of convex polygons and related problems
- Searching for segments with largest relative overlap
- scientific article; zbMATH DE number 4131656 (Why is no real title available?)
- A polynomial-time algorithm for computing the resilience of arrangements of ray sensors
- OVERLAYING SURFACE MESHES, PART I: ALGORITHMS
- Filling polyhedral molds
- Geometric algorithms for finding a point in the intersection of balls
- Constructing arrangements optimally in parallel
- An intersection-sensitive algorithm for snap rounding
- Applications of random sampling to on-line algorithms in computational geometry
- Topological sweep of the complete graph
- An algebraic algorithm to compute the exact general sweep boundary of a 2D curved object
- Partitioning arrangements of lines. II: Applications
- Counting and representing intersections among triangles in three dimensions
- External-memory algorithms for processing line segments in geographic information systems
- MINIMUM SEPARATION IN WEIGHTED SUBDIVISIONS
- Counting and cutting cycles of lines and rods in space
- New upper bounds for generalized intersection searching problems
- Topologically sweeping visibility complexes via pseudotriangulations
- A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums
- An introduction to randomization in computational geometry
- Cache-Oblivious Red-Blue Line Segment Intersection
- Line-segment intersection made in-place
- OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS
- scientific article; zbMATH DE number 1445286 (Why is no real title available?)
- Fast dynamic intersection searching in a set of isothetic line segments
- Minimum-link paths among obstacles in the plane
- Bold graph drawings
- Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments
- Efficient algorithms for counting and reporting pairwise intersections between convex polygons
- Infimaximal Frames: A Technique for Making Lines Look Like Segments
- Every graph admits an unambiguous bold drawing
- On the general motion-planning problem with two degrees of freedom
- Efficient view point selection for silhouettes of convex polyhedra
- Untangling planar curves
- An introduction to randomized algorithms
- RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
- Decision Trees for Geometric Models
- Using sparsification for parametric minimum spanning tree problems
- scientific article; zbMATH DE number 1424323 (Why is no real title available?)
- Concyclic intervals in the plane
- Locating an obnoxious line among planar objects
- Polyhedral circuits and their applications
- Path planning in a weighted planar subdivision under the Manhattan metric
- The maximum-level vertex in an arrangement of lines
- The touring rays and related problems
- ON COMPUTING TRANSLATIONAL SWEPT VOLUMES
- Quick algorithm for reconstructing line object adjacency relations
- Techniques and open questions in computational convex analysis
- Tight bounds on the solutions of multidimensional divide-and-conquer maximin recurrences
- Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
- An algorithm for intersections determination among geometric buffers using skip lists
- scientific article; zbMATH DE number 7561502 (Why is no real title available?)
- Reporting bichromatic segment intersections from point sets
- RED-BLUE SEPARABILITY PROBLEMS IN 3D
- Geometric multicut: shortest fences for separating groups of objects in the plane
- An optimal online algorithm for halfplane intersection
- scientific article; zbMATH DE number 432986 (Why is no real title available?)
- Complexity of projected images of convex subdivisions
- On finding ordinary or monochromatic intersection points
- Combinatorics of intervals in the plane. I: Trapezoids
- Sweep methods for parallel computational geometry
- Isomorphism of spiral polygons
- An elementary algorithm for reporting intersections of red/blue curve segments
- Separability by two lines and by nearly straight polygonal chains
- Reporting intersections among thick objects.
This page was built for publication: An optimal algorithm for intersecting line segments in the plane
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4302817)
