8

Basically the formulation of the problem I'd like to solve is very simple. Given 2 simple polygons (without self-intersections) report all intersecting edge pairs in O(n+k) time, where n - is a total number of edges, k - number of intersections between two polygons.

It is very important to stay within mentioned time hardness. What does surprise me, that I could hardly find information on this subject. Polygon intersections seems to be so natural and important problem. Anyway at the moment I don't have a clue if it is even possible to do it in O(n+k).

Can please someone help with lower bounds for this problem?

Some additional points on my question:

  1. Polygon clipping with set operations and intersection reporting (about which my question was) seems to be slightly different problems - Having found intersecting edges you would have to constract a polygon which is a result of clipping/set operation.
  2. An approach based on segment intersection algorithm won't work for me. As it is proved that worst case takes O(nlogn+k).
  3. I'm not insisting that an algorithm with such hardness exist - it may not. But in this case I would really appreciate if someone could provide a lower bound proof for my problem - tons of papers provide some very interesting algorithm (usually with O(nlogn+k) complexity) but for some reason don't mention the lower bound.
Aron Ahmadia
  • 6,951
  • 4
  • 34
  • 54
Sergei Ivanov
  • 81
  • 1
  • 2

2 Answers2

8

The $\mathcal{O}(n+k)$ algorithms seem to be limited to convex polygons. The fastest algorithms that I have found here and here have approximately $\mathcal{O}(n\log(n))$ algorithms. According to this, the problem of simple polygon intersection is linear time transformable to line-segment intersection testing, which has an optimal bound of approximately $\mathcal{O}(n\log(n) + k)$ according to this article.

dmckee --- ex-moderator kitten
  • 1,115
  • 8
  • 17
Paul
  • 12,045
  • 7
  • 56
  • 129
  • 1
    If $n$ is the (total) number of edges, it is impossible to get $\mathcal{O}(n\log(n))$ running time, as in the worst case, you may have $\Theta(n^2)$ number of intersections. What they state in the abstract of the article that I can see (the link to the other one is broken) is that they can obtain $\mathcal{O}((n+I)\times\log_2(n+I))$, where $I$ is the number of intersection points (and $n$ is called $k$ in the abstract). – HelloGoodbye Mar 29 '20 at 00:06
3

In the general case, this cannot be done in $O(n+k)$ time, as there can be as many as $4\lfloor\frac{n}{2}\rfloor\lfloor\frac{k}{2}\rfloor$, i.e., Θ(nk) intersection points.

If the two polygons are convex, however, you can find the intersections in $O(n+k)$ time.

See Computational Geometry in C Second Edition, page 253, or Shamos (1978), page 116.

HelloGoodbye
  • 131
  • 3