<p><strong>TL;DR: Yes, in principle this can be done in <span class="math-container">$O(n)$</span> and the book is inaccurate.</strong></p>
<p>This is quite subtle, the first statement is not correct. Returning <em>all</em> intersections has a <span class="math-container">$\Omega(n\log n)$</span> lower bound, but <strong>detecting</strong> intersections (if any) can be done in <span class="math-container">$O(n)$</span> time.</p>
<p>Chazelle <a href="https://www.cs.princeton.edu/%7Echazelle/pubs/polygon-triang.pdf" rel="nofollow noreferrer">proved</a> that detecting a <em>polygon curve self intersection</em> can be done in <span class="math-container">$O(n)$</span> time via his linear time triangulation. You simply assume a curve is not self intersecting and try to triangulate it. The algorithm will detect if something goes wrong (because of the self intersection).</p>
<p>You can reduce detecting if two polygons <span class="math-container">$P,Q$</span> intersect into detecting if a polygonal curve <span class="math-container">$R$</span> self intersects by &quot;connecting&quot; the two polygons in <span class="math-container">$O(n)$</span> time. I remember this trick from a paper by David Mount but I do not remember the reference. The proof idea is connecting the two polygons by a very thin slab (in red) and checking if the resulting polygonal curve self intersects:</p>
<p><a href="https://i.sstatic.net/k4K5B.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/k4K5B.png" alt="Connecting two polygons with a thin red slab" /></a></p>

CC BY-SA 4.0
2023-05-23T17:28:27.963Z
Thanks for the great answer. It turns out Chazelle actually explicitly mentions it in his paper: "From this we easily derive a new result: testing whether two simple polygons intersect in linear time...". He also mentions that the algorithm can indeed be used to check whether a polygonal curve is a simple, as you mentioned in your post (this isn't automatically the case of course, there exist triangulation algorithms which require simplicity but can't easily be changed to complain if the input isn't simple, though in the case of Chazelle's O(n) algorithm, this is apparently the case).
Lieven
CC BY-SA 4.0
2023-05-23T10:41:53.550Z
2023-05-23T10:41:53.550Z
user3508551
<p>In the book &quot;Spatial Databases: With Application to GIS (The Morgan Kaufmann Series in Data Management Systems)&quot;, there's a section on simple polygon intersection detection , and it mentions</p>
<blockquote>
<p>...The cost is dominated by the LINEINTERSECTIONTEST algorithm. Therefore, detecting whether two simple polygons intersect is
O(n log n). This is optimal...</p>
</blockquote>
<p>But it doesn't provide a source for the claim that this is optimal. Does anyone know if this is indeed the case, and if so, how it's proven?</p>

CC BY-SA 4.0
2023-05-23T08:52:19.390Z
This is not a research level question, so it does not belong to the website. If $P_1, P_2$ are polygons with $n_1, n_2$ vertices respectively with $n=n_1+n_2$ , then you can compute the union, intersection, and symetric difference in $O(n\log n)$ using sweeping + map overlays. This is standard in most computational geometry books (see for example the Berg book, Chapter 2).
user3508551
CC BY-SA 4.0
2023-05-23T08:54:14.047Z
Your second comment is also false. I had a look at the Chapter you mention. The authors correctly state that they give algorithms for computing *the* intersection of two convex polygons in $O(n)$, not *if* there is an intersection. The classic Chazelle $O(\log n)$ algorithm is for detecting *if* the polygons intersect, not for computing their intersection. The intersection complexity can be $\Omega(n)$ and so $O(n)$ is indeed optimal.
user3508551
CC BY-SA 4.0
2023-05-23T09:03:16.243Z
Thanks for your answer. I think you're misunderstanding my question. I understand why the algorithm they proposed is O(n log n), I'm curious about their claim that this is optimal. This seems far from trivial to me, so if it's indeed true, then I'm curious to see a proof.
Lieven
CC BY-SA 4.0
2023-05-23T09:07:42.580Z
"In the next section, it provides a linear time algorithm to determine whether" This is just false, this is not what the authors say. The authors write: "We present a simple algorithm for computing **the** intersection of two convex polygons, which achieves the optimal O(n) complexity"
user3508551
CC BY-SA 4.0
2023-05-23T09:10:36.247Z
That doesn't proof it. The line segment intersection test works with any arbitrary set of segments, while in our case, we know the segments form two simple polygons, so we have a lot more information.
Lieven
CC BY-SA 4.0
2023-05-23T09:16:22.720Z
You're right, I misread the part about convex polygon intersection, but that wasn't the main part of my question, the main question still stands.
Lieven
<cg.comp-geom><polygon>
Complexity of polygon intersection test
Lieven
# Complexity of polygon intersection test

(Asked by: username_0 on 2023-05-22)

In the book "Spatial Databases: With Application to GIS (The Morgan Kaufmann Series in Data Management Systems)", there's a section on simple polygon intersection detection , and it mentions

> ...The cost is dominated by the LINEINTERSECTIONTEST algorithm. Therefore, detecting whether two simple polygons intersect is
> O(n log n). This is optimal...

But it doesn't provide a source for the claim that this is optimal. Does anyone know if this is indeed the case, and if so, how it's proven?

**Tags:** cg.comp-geom, polygon

> **Comments:**
> **username_1**: This is not a research level question, so it does not belong to the website. If $P_1, P_2$ are polygons with $n_1, n_2$ vertices respectively with $n=n_1+n_2$ , then you can compute the union, intersection, and symetric difference in $O(n\log n)$ using sweeping + map overlays. This is standard in most computational geometry books (see for example the Berg book, Chapter 2).  
> **username_1**: Your second comment is also false. I had a look at the Chapter you mention. The authors correctly state that they give algorithms for computing *the* intersection of two convex polygons in $O(n)$, not *if* there is an intersection. The classic Chazelle $O(\log n)$ algorithm is for detecting *if* the polygons intersect, not for computing their intersection. The intersection complexity can be $\Omega(n)$ and so $O(n)$ is indeed optimal.  
> **username_0**: Thanks for your answer. I think you're misunderstanding my question. I understand why the algorithm they proposed is O(n log n), I'm curious about their claim that this is optimal. This seems far from trivial to me, so if it's indeed true, then I'm curious to see a proof.  
> **username_1**: "In the next section, it provides a linear time algorithm to determine whether" This is just false, this is not what the authors say. The authors write: "We present a simple algorithm for computing **the** intersection of two convex polygons, which achieves the optimal O(n) complexity"  
> **username_0**: That doesn't proof it. The line segment intersection test works with any arbitrary set of segments, while in our case, we know the segments form two simple polygons, so we have a lot more information.  
> **username_0**: You're right, I misread the part about convex polygon intersection, but that wasn't the main part of my question, the main question still stands.  

---

## 1 answers

### Answer by username_1 on 2023-05-23. Score: 2 | Accepted answer

**TL;DR: Yes, in principle this can be done in $O(n)$ and the book is inaccurate.**

This is quite subtle, the first statement is not correct. Returning *all* intersections has a $\Omega(n\log n)$ lower bound, but **detecting** intersections (if any) can be done in $O(n)$ time.

Chazelle [proved](https://www.cs.princeton.edu/%7Echazelle/pubs/polygon-triang.pdf) that detecting a *polygon curve self intersection* can be done in $O(n)$ time via his linear time triangulation. You simply assume a curve is not self intersecting and try to triangulate it. The algorithm will detect if something goes wrong (because of the self intersection).

You can reduce detecting if two polygons $P,Q$ intersect into detecting if a polygonal curve $R$ self intersects by "connecting" the two polygons in $O(n)$ time. I remember this trick from a paper by David Mount but I do not remember the reference. The proof idea is connecting the two polygons by a very thin slab (in red) and checking if the resulting polygonal curve self intersects:

[![Connecting two polygons with a thin red slab](https://i.sstatic.net/k4K5B.png)](https://i.sstatic.net/k4K5B.png)

> **Comments:**
> **username_0**: Thanks for the great answer. It turns out Chazelle actually explicitly mentions it in his paper: "From this we easily derive a new result: testing whether two simple polygons intersect in linear time...". He also mentions that the algorithm can indeed be used to check whether a polygonal curve is a simple, as you mentioned in your post (this isn't automatically the case of course, there exist triangulation algorithms which require simplicity but can't easily be changed to complain if the input isn't simple, though in the case of Chazelle's O(n) algorithm, this is apparently the case).  

---

