2
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ 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). $\endgroup$
    – user3508551
    May 23 at 8:52
  • $\begingroup$ 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. $\endgroup$
    – user3508551
    May 23 at 8:54
  • $\begingroup$ 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. $\endgroup$
    – Lieven
    May 23 at 9:03
  • $\begingroup$ "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" $\endgroup$
    – user3508551
    May 23 at 9:07
  • $\begingroup$ 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. $\endgroup$
    – Lieven
    May 23 at 9:10

1 Answer 1

Reset to default
2
$\begingroup$

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 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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – Lieven
    May 23 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.