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