7
$\begingroup$

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.
| cite | improve this question | |
$\endgroup$
8
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – HelloGoodbye Mar 29 at 0:06
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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