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

<p>You are unlikely to solve the problem significantly faster than $O(n^2)$ because it is equivalent in difficulty to <a href="https://en.wikipedia.org/wiki/3SUM">3SUM</a> — see the original paper on 3SUM hardness, "<a href="http://dx.doi.org/10.1016/0925-7721(95)00022-2">On a class of $O(n^2)$ problems in computational geometry"</a>, by Gajentaan and Overmars (CGTA 1995).</p>

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

CC BY-SA 3.0
2014-08-20T20:31:20.203Z
2014-08-20T20:31:20.203Z
David Eppstein
<p>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).)</p>

CC BY-SA 3.0
2014-08-20T20:01:47.873Z
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?
Shahab
CC BY-SA 3.0
2014-08-20T20:03:59.923Z
n^3 is efficient enough.
Paul Reiners
CC BY-SA 3.0
2014-08-20T20:17:15.550Z
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.
Shahab
CC BY-SA 3.0
2014-08-20T20:27:32.580Z
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.
Paul Reiners
CC BY-SA 3.0
2014-08-20T20:34:50.013Z
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.
Shahab
<computational-geometry><polygon>
Finding a point outside of each of a set of polygons in a bounded space
Paul Reiners
# Finding a point outside of each of a set of polygons in a bounded space

(Asked by: username_0 on 2014-08-20)

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

**Tags:** computational-geometry, polygon
> **Comments:**
> **username_1**: 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?  
> **username_0**: n^3 is efficient enough.  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2014-08-20. Score: 5 | Accepted answer

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](https://en.wikipedia.org/wiki/3SUM) — see the original paper on 3SUM hardness, "[On a class of $O(n^2)$ problems in computational geometry"](http://dx.doi.org/10.1016/0925-7721(95)00022-2), 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.


---

