Reporting and counting segment intersections
From MaRDI portal
Publication:1821557
DOI10.1016/0022-0000(86)90025-5zbMath0616.68042OpenAlexW2051017380MaRDI QIDQ1821557
Publication date: 1986
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(86)90025-5
Related Items
Extremal polygon containment problems, A fast planar partition algorithm. I, Orthogonal queries in segments, Line arrangements and range search, Parallel computational geometry, Partitioning arrangements of lines. II: Applications, Computing the convex hull in a hammock, A tight upper bound for the number of intersections between two rectangulars paths, On counting pairs of intersecting segments and off-line triangle range searching, Approximation schemes for the parametric knapsack problem, Line-segment intersection reporting in parallel, Approximating the Packedness of Polygonal Curves, A tail estimate for Mulmuley's segment intersection algorithm, Constructing arrangements optimally in parallel, New lower bounds for Hopcroft's problem, An improved upper bound on the number of intersections between two rectangular paths, Computing the update of the repeated median regression line in linear time, Approximating the packedness of polygonal curves, Counting and representing intersections among triangles in three dimensions, Algorithms for bichromatic line-segment problems and polyhedral terrains
Cites Work
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Finding the intersection of two convex polyhedra
- Relational topology
- Algorithms for Reporting and Counting Geometric Intersections
- Comments on “algorithms for reporting and counting geometric intersections”
- Plane-sweep algorithms for intersecting geometric figures
- Optimal Search in Planar Subdivisions
