Reporting all intersection points, generalized segments: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 40: Line 40:
[[File:Line segment intersection - Reporting all intersection points, generalized segments - Space.png|1000px]]
[[File:Line segment intersection - Reporting all intersection points, generalized segments - Space.png|1000px]]


== Space-Time Tradeoff Improvements ==  
== Time-Space Tradeoff ==  


[[File:Line segment intersection - Reporting all intersection points, generalized segments - Pareto Frontier.png|1000px]]
[[File:Line segment intersection - Reporting all intersection points, generalized segments - Pareto Frontier.png|1000px]]

Revision as of 14:41, 15 February 2023

Description

In this case, the segments are generalized (i.e. have algebraic degree ≥1); we still wish to report all points of intersection.

Related Problems

Subproblem: Reporting all intersection points, line segments

Related: Reporting all intersection points, convex polygons, Reporting all intersection points, general polygons, Counting number of intersection points, line segments

Parameters

n: number of line segments

k: number of points of intersection

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Jean-Daniel Boissonnat and Franco P. Preparata. 1997 $O( n log n + k log n)$ $O(n)$ Exact Deterministic Time & Space
Balaban. 1995 $O( nlog n + k )$ $O(n)$ Exact Deterministic Time & Space
Boissonnat; Snoeyink 1999 $O( nlog n + k )$ $O(n)$ Exact Deterministic Time & Space

Time Complexity Graph

Line segment intersection - Reporting all intersection points, generalized segments - Time.png

Space Complexity Graph

Line segment intersection - Reporting all intersection points, generalized segments - Space.png

Time-Space Tradeoff

Line segment intersection - Reporting all intersection points, generalized segments - Pareto Frontier.png

References/Citation

https://dl.acm.org/citation.cfm?id=304991

https://dl.acm.org/doi/10.1145/304893.304991)