1
$\begingroup$

I know there are algorithms for finding a point inside a simple polygon. Given a set of polygons inside a rectangle (think a bunch of polygons on a computer screen), is there an efficient algorithm for finding a point that is inside the rectangle but not inside any of the specified polygons? (Note that these polygons don't overlap, but may share a common border (or part of a border).)

$\endgroup$
  • $\begingroup$ What do you mean by efficient? Without thinking too much, I can think of an $O(n^3)$ algorithm (with $n$ being the total number of points in all the polygons altogether) that seems to work. But is $n^3$ efficient? $\endgroup$ – Shahab Aug 20 '14 at 20:01
  • $\begingroup$ n^3 is efficient enough. $\endgroup$ – Paul Reiners Aug 20 '14 at 20:03
  • $\begingroup$ I have to think of the details but the gist of it is that you construct all possible edge crossings (at most $O(n^2)$ points). Now, for each point $P$ you check if $P$ is inside your rectangle but outside or on the border of all the polygons. If such $P$ is found, you have to check if there is a point very close to $P$ (essentially $P+\varepsilon$) that falls outside all polygons. Both those checks can be done in $O(n)$ which would essentially give you an $O(n^3)$ algorithm. I understand that this is a hand-wavey way but I think the details can be worked out. $\endgroup$ – Shahab Aug 20 '14 at 20:17
  • $\begingroup$ What do you mean by edge crossing? No pair of polygons intersect each other, although they may share a border or part of a border. $\endgroup$ – Paul Reiners Aug 20 '14 at 20:27
  • $\begingroup$ Okay, I didn't see in the problem description that the polygons do not intersect. So I assumed the general case where they can intersect. Under the new condition, I think the algorithm would be faster ($O(n^2)$) because the number of candidates to check would reduce to $O(n)$ points (from its previous $O(n^2)$ points). Using this added condition, the only points $P$ that you have to do above check on them are the vertices of the polygons. $\endgroup$ – Shahab Aug 20 '14 at 20:34
5
$\begingroup$

If the polygons can overlap, the problem can be solved in $O(n^2)$ time (where $n$ is the number of sides of the polygons in total) by constructing the arrangement of line segments and maintaining as you construct it the number of polygons that cover each cell of the arrangement. There are $O(n^2)$ cells, arrangements can be constructed in $O(n^2)$ time, and it takes constant time per cell to maintain the covering number because it differs by one from the number of any neighboring cell.

You are unlikely to solve the problem significantly faster than $O(n^2)$ because it is equivalent in difficulty to 3SUM — see the original paper on 3SUM hardness, "On a class of $O(n^2)$ problems in computational geometry", by Gajentaan and Overmars (CGTA 1995).

With your specification that the polygons cannot overlap, the same approach works in $O(n\log n)$ time using an output-sensitive arrangement construction algorithm.

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