View source for Reporting all intersection points, convex polygons

{{DISPLAYTITLE:Reporting all intersection points, convex polygons (Line segment intersection)}}
== Description == 

In this case, we are supplied with a list of convex polygons, and we wish to report all regions of intersection.

== Related Problems == 

Generalizations: [[Reporting all intersection points, general polygons]]

Related: [[Reporting all intersection points, line segments]], [[Reporting all intersection points, generalized segments]], [[Counting number of intersection points, line segments]]

== Parameters == 

$n$: number of line segments

$k$: number of points of intersection

== Table of Algorithms == 

{| class="wikitable sortable"  style="text-align:center;" width="100%"

! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference

|-

| [[NIEVERGELT. J.. AND PREPARATA (Section 3) (Reporting all intersection points, convex polygons Line segment intersection)|NIEVERGELT. J.. AND PREPARATA (Section 3)]] || 1982 || $O( n \log n + k )$ || $O(n)$ || Exact || Deterministic || [https://pdfs.semanticscholar.org/a571/cc92218132a1b0e65c2adbf663c79d015737.pdf Time] & [https://courses.cs.duke.edu/cps234/spring04/papers/NP82.pdf Space]
|-
|}

== Time Complexity Graph == 

[[File:Line segment intersection - Reporting all intersection points, convex polygons - Time.png|1000px]]

== References/Citation == 

https://pdfs.semanticscholar.org/a571/cc92218132a1b0e65c2adbf663c79d015737.pdf