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 12: Line 12:
== Parameters ==  
== Parameters ==  


n: number of line segments
$n$: number of line segments


k: number of points of intersection
$k$: number of points of intersection


== Table of Algorithms ==  
== Table of Algorithms ==  
Line 24: Line 24:
|-
|-


| [[Jean-Daniel Boissonnat and Franco P. Preparata.  (Reporting all intersection points, generalized segments Line segment intersection)|Jean-Daniel Boissonnat and Franco P. Preparata. ]] || 1997 || $O( n log n + k log n)$ || $O(n)$ || Exact || Deterministic || [https://epubs.siam.org/doi/abs/10.1137/S0097539797329373 Time] & [https://epubs.siam.org/doi/epdf/10.1137/S0097539797329373 Space]
| [[Jean-Daniel Boissonnat and Franco P. Preparata.  (Reporting all intersection points, generalized segments Line segment intersection)|Jean-Daniel Boissonnat and Franco P. Preparata. ]] || 1997 || $O(n \log n + k \log n)$ || $O(n)$ || Exact || Deterministic || [https://epubs.siam.org/doi/abs/10.1137/S0097539797329373 Time] & [https://epubs.siam.org/doi/epdf/10.1137/S0097539797329373 Space]
|-
|-
| [[Balaban. (Reporting all intersection points, generalized segments Line segment intersection)|Balaban.]] || 1995 || $O( nlog n + k )$ || $O(n)$ || Exact || Deterministic || [https://dl.acm.org/doi/pdf/10.1145/220279.220302 Time & Space]
| [[Balaban. (Reporting all intersection points, generalized segments Line segment intersection)|Balaban.]] || 1995 || $O(n \log n + k )$ || $O(n)$ || Exact || Deterministic || [https://dl.acm.org/doi/pdf/10.1145/220279.220302 Time & Space]
|-
|-
| [[Boissonnat; Snoeyink (Reporting all intersection points, generalized segments Line segment intersection)|Boissonnat; Snoeyink]] || 1999 || $O( nlog n + k )$ || $O(n)$ || Exact || Deterministic || [https://dl.acm.org/citation.cfm?id=304991 Time & Space]
| [[Boissonnat; Snoeyink (Reporting all intersection points, generalized segments Line segment intersection)|Boissonnat; Snoeyink]] || 1999 || $O(n \log n + k )$ || $O(n)$ || Exact || Deterministic || [https://dl.acm.org/citation.cfm?id=304991 Time & Space]
|-
|-
|}
|}

Revision as of 09:19, 10 April 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(n \log n + k )$ $O(n)$ Exact Deterministic Time & Space
Boissonnat; Snoeyink 1999 $O(n \log 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)

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Reporting_all_intersection_points,_generalized_segments&oldid=47086"