<p>Here's an argument that you need time quadratic in the number of polygons. More precisely,
you should not be able to find containing pairs among <span class="math-container">$n$</span> <span class="math-container">$k$</span>-sided polygons in time <span class="math-container">$O(n^{2-\epsilon})$</span>, for any <span class="math-container">$k=O(n^{\delta})$</span> and any <span class="math-container">$\epsilon,\delta&gt;0$</span> It's a reduction from the orthogonal vectors problem, the problem of finding two disjoint binary vectors among a set of <span class="math-container">$n$</span> <span class="math-container">$k$</span>-dimensional binary vectors, for which the non-existence of an algorithm with time <span class="math-container">$O(n^{2-\epsilon})$</span> is a standard conjecture in fine-grained complexity (see e.g.  Abboud et al, "<a href="https://dl.acm.org/citation.cfm?id=3188938" rel="nofollow noreferrer">More consequences of falsifying SETH and the orthogonal vectors conjecture</a>"). Here orthogonality is measured in <span class="math-container">$\mathbb{Z}^k$</span>, i.e. it means that the vectors have disjoint subsets of nonzero coordinates.</p>

<p>Given a set of vectors among which we wish to find an orthogonal pair, consider a regular <span class="math-container">$k$</span>-gon <span class="math-container">$P$</span>, whose vertices correspond to the coefficients of our vectors. For each vector <span class="math-container">$x$</span> construct a polygon <span class="math-container">$p(x)$</span> as the convex hull of the <span class="math-container">$k$</span>-gon vertices for which <span class="math-container">$x$</span> has a nonzero coefficient. To make sure that none of these polygons contains each other, shrink each <span class="math-container">$k$</span>-gon by a factor <span class="math-container">$1-\gamma |x|$</span> for some very small number <span class="math-container">$\gamma$</span>, so that when one vector is dominated by another its polygon is shrunk more.</p>

<p>Next, form two more regular <span class="math-container">$k$</span>-gons <span class="math-container">$Q$</span> and <span class="math-container">$R$</span>, concentric with <span class="math-container">$P$</span>, where <span class="math-container">$Q$</span> is slightly smaller than <span class="math-container">$P$</span> (so that all its vertices are inside the shrunken copies of vertices of <span class="math-container">$P$</span>) and <span class="math-container">$R$</span> is slightly bigger (both close enough that the construction below produces convex polygons). For each vector <span class="math-container">$x$</span>, construct a second polygon <span class="math-container">$q(x)$</span>, a convex <span class="math-container">$k$</span>-gon that, on each ray from the origin through a vertex of <span class="math-container">$P$</span>, <span class="math-container">$Q$</span>, and <span class="math-container">$R$</span>, chooses either a vertex of <span class="math-container">$Q$</span> or <span class="math-container">$R$</span>: a vertex of <span class="math-container">$Q$</span> when the corresponding coefficient of <span class="math-container">$x$</span> is nonzero, and a vertex of <span class="math-container">$R$</span> when it is zero.
We can make sure that all vectors have at least one zero coefficient in order to ensure that no <span class="math-container">$q(x)$</span> is contained inside a <span class="math-container">$p(y)$</span>, and we can do the same variable-shrinking trick to ensure that no two <span class="math-container">$q$</span>'s are nested.</p>

<p>With this construction, the only remaining containments of polygons are that a polygon <span class="math-container">$q(x)$</span> contains another polygon <span class="math-container">$p(y)$</span>. This happens if and only if <span class="math-container">$x$</span> and <span class="math-container">$y$</span> are orthogonal. So if we could solve your polygon question in sub-quadratic time, we could also solve the orthogonal vectors problem in sub-quadratic time, conjectured to be impossible.</p>

CC BY-SA 4.0
2020-01-08T16:48:57.753Z
Thank you very much for you quick response!! So, I was looking at the construction and it looks very nice. I just have a couple clarifications/questions. (1) At the shrinking process |x| is the number of 1s in the vector, so the more 1s the more it is shrunk? And thus, the dominated polygon is shrunk less (instead of more that is written), right? (2) I didn't get the catch with the fact that the q(x) polygons are non-convex. How do we go to convex polygons? Is there some argument related with k-gon R and how "much bigger" that is?
ioannis
CC BY-SA 4.0
2020-01-08T20:15:55.430Z
(1) Yes. The p's with more 1's stick out at the points where they differ but stick in at the points where they both have 1's because of the shrinkage, so no two p's are nested. (2) I missed the part where the polygons should all be convex but by choosing the sizes of P, Q, and R more carefully they can be made all convex without affecting the overall construction; I will edit the answer to fix that.
David Eppstein
CC BY-SA 4.0
2020-01-08T02:09:21.487Z
2020-01-08T20:16:45.150Z
2020-01-08T20:16:45.150Z
David Eppstein
<p>I have the following problem which came as a subproblem in some work I was doing and I am completely stuck. 
Note that I am interested in it only in terms of worst case time complexity (not heuristics or anything else).</p>

<p>Given is a set <span class="math-container">$\mathcal{P}$</span> of <span class="math-container">$m$</span> convex polygons with <span class="math-container">$n$</span> overall vertices.</p>

<p><strong>PROB:</strong> Find the set <span class="math-container">$Z \subset \mathcal{P}$</span>, such that for any <span class="math-container">$Q \in Z$</span>, there exists a <span class="math-container">$P \in \mathcal{P}\setminus \{Q\}$</span> with <span class="math-container">$P$</span> contained in <span class="math-container">$Q$</span>. <em>(i.e. "Find the polygons which contain at least one polygon")</em></p>

<p><em>In the following example, the set Z would consist of the 4 highlighted polygons</em>
<a href="https://i.sstatic.net/QOWd7.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/QOWd7.png" alt="In this example, the set Z would consist of the 4 highlighted polygons."></a></p>

<p>Some thoughts I had were:</p>

<ol>
<li><p>A first idea was to plane sweep with all vertices as events. Every time an event would come we would check the polygons it belongs to and mark them. When the event would be the end of a polygon we could verify that if this belongs to any polygon or not.
The problem is that a query event could take <span class="math-container">$O(m)$</span> as it could be inside <span class="math-container">$O(m)$</span> polygons (assuming an interval tree DS where an "all_overlap" operation takes <span class="math-container">$O(\min\{m,c\cdot \log m\})$</span> time, where <span class="math-container">$c$</span> is the number of overlaps - containing polygons). Moreover, I believe we can create a worst case instance where <span class="math-container">$O(n)$</span> events have <span class="math-container">$O(m)$</span> overlaps. So, with this approach it seems that we could end up with an <span class="math-container">$O(mn + n\log n)$</span> time complexity.</p></li>
<li><p>I started having some thoughts for a more elaborate plane sweep to use the pairwise polygon intersections but since this can be <span class="math-container">$\Theta(m^2)$</span> in the worst case, I didn't further look on that.</p></li>
<li><p>Another thought was to make an algorithm using range search queries for the convex polygons. If we triangulated every polygon, having <span class="math-container">$O(n)$</span> triangles, we could check the containment. Unfortunately, taking a "brief look", I didn't find very "positive" results for answering fast range queries with anything different than rectangles, e.g. triangles. Although I didn't yet delve very deep into it. </p></li>
</ol>

<p>I would be extremely happy to have an <span class="math-container">$O((1+|Z|) n\log^2 n)$</span> time algorithm. I am not positive about that anymore. So, I would be happy with any algorithm or ideas how to further proceed.</p>

<p>Finally, and perhaps as a starting point, one could consider the simplified decision problem. </p>

<p><strong>PROB*:</strong> Does there exist <span class="math-container">$Q \in \mathcal{P}$</span> such that there exists a <span class="math-container">$P \in \mathcal{P}\setminus \{Q\}$</span> with <span class="math-container">$P$</span> contained in <span class="math-container">$Q$</span>. </p>

<p>What would be an efficient algorithm for that?</p>

<ds.algorithms><computational-geometry><polygon><convex-hull>
Convex polygons inclusion relation
ioannis
# Convex polygons inclusion relation

(Asked by: username_0 on 2020-01-07)

I have the following problem which came as a subproblem in some work I was doing and I am completely stuck.
Note that I am interested in it only in terms of worst case time complexity (not heuristics or anything else).

Given is a set $\mathcal{P}$ of $m$ convex polygons with $n$ overall vertices.

**PROB:** Find the set $Z \subset \mathcal{P}$, such that for any $Q \in Z$, there exists a $P \in \mathcal{P}\setminus \{Q\}$ with $P$ contained in $Q$. *(i.e. "Find the polygons which contain at least one polygon")*

*In the following example, the set Z would consist of the 4 highlighted polygons*
[![In this example, the set Z would consist of the 4 highlighted polygons.](https://i.sstatic.net/QOWd7.png)](https://i.sstatic.net/QOWd7.png)

Some thoughts I had were:

1. A first idea was to plane sweep with all vertices as events. Every time an event would come we would check the polygons it belongs to and mark them. When the event would be the end of a polygon we could verify that if this belongs to any polygon or not.
   The problem is that a query event could take $O(m)$ as it could be inside $O(m)$ polygons (assuming an interval tree DS where an "all\_overlap" operation takes $O(\min\{m,c\cdot \log m\})$ time, where $c$ is the number of overlaps - containing polygons). Moreover, I believe we can create a worst case instance where $O(n)$ events have $O(m)$ overlaps. So, with this approach it seems that we could end up with an $O(mn + n\log n)$ time complexity.
2. I started having some thoughts for a more elaborate plane sweep to use the pairwise polygon intersections but since this can be $\Theta(m^2)$ in the worst case, I didn't further look on that.
3. Another thought was to make an algorithm using range search queries for the convex polygons. If we triangulated every polygon, having $O(n)$ triangles, we could check the containment. Unfortunately, taking a "brief look", I didn't find very "positive" results for answering fast range queries with anything different than rectangles, e.g. triangles. Although I didn't yet delve very deep into it.

I would be extremely happy to have an $O((1+|Z|) n\log^2 n)$ time algorithm. I am not positive about that anymore. So, I would be happy with any algorithm or ideas how to further proceed.

Finally, and perhaps as a starting point, one could consider the simplified decision problem.

**PROB\*:** Does there exist $Q \in \mathcal{P}$ such that there exists a $P \in \mathcal{P}\setminus \{Q\}$ with $P$ contained in $Q$.

What would be an efficient algorithm for that?

**Tags:** ds.algorithms, computational-geometry, polygon, convex-hull


---

## 1 answers

### Answer by username_1 on 2020-01-08. Score: 3 | Accepted answer

Here's an argument that you need time quadratic in the number of polygons. More precisely,
you should not be able to find containing pairs among $n$ $k$-sided polygons in time $O(n^{2-\epsilon})$, for any $k=O(n^{\delta})$ and any $\epsilon,\delta>0$ It's a reduction from the orthogonal vectors problem, the problem of finding two disjoint binary vectors among a set of $n$ $k$-dimensional binary vectors, for which the non-existence of an algorithm with time $O(n^{2-\epsilon})$ is a standard conjecture in fine-grained complexity (see e.g. Abboud et al, "[More consequences of falsifying SETH and the orthogonal vectors conjecture](https://dl.acm.org/citation.cfm?id=3188938)"). Here orthogonality is measured in $\mathbb{Z}^k$, i.e. it means that the vectors have disjoint subsets of nonzero coordinates.

Given a set of vectors among which we wish to find an orthogonal pair, consider a regular $k$-gon $P$, whose vertices correspond to the coefficients of our vectors. For each vector $x$ construct a polygon $p(x)$ as the convex hull of the $k$-gon vertices for which $x$ has a nonzero coefficient. To make sure that none of these polygons contains each other, shrink each $k$-gon by a factor $1-\gamma |x|$ for some very small number $\gamma$, so that when one vector is dominated by another its polygon is shrunk more.

Next, form two more regular $k$-gons $Q$ and $R$, concentric with $P$, where $Q$ is slightly smaller than $P$ (so that all its vertices are inside the shrunken copies of vertices of $P$) and $R$ is slightly bigger (both close enough that the construction below produces convex polygons). For each vector $x$, construct a second polygon $q(x)$, a convex $k$-gon that, on each ray from the origin through a vertex of $P$, $Q$, and $R$, chooses either a vertex of $Q$ or $R$: a vertex of $Q$ when the corresponding coefficient of $x$ is nonzero, and a vertex of $R$ when it is zero.
We can make sure that all vectors have at least one zero coefficient in order to ensure that no $q(x)$ is contained inside a $p(y)$, and we can do the same variable-shrinking trick to ensure that no two $q$'s are nested.

With this construction, the only remaining containments of polygons are that a polygon $q(x)$ contains another polygon $p(y)$. This happens if and only if $x$ and $y$ are orthogonal. So if we could solve your polygon question in sub-quadratic time, we could also solve the orthogonal vectors problem in sub-quadratic time, conjectured to be impossible.

> **Comments:**
> **username_0**: Thank you very much for you quick response!! So, I was looking at the construction and it looks very nice. I just have a couple clarifications/questions. (1) At the shrinking process |x| is the number of 1s in the vector, so the more 1s the more it is shrunk? And thus, the dominated polygon is shrunk less (instead of more that is written), right? (2) I didn't get the catch with the fact that the q(x) polygons are non-convex. How do we go to convex polygons? Is there some argument related with k-gon R and how "much bigger" that is?  
> **username_1**: (1) Yes. The p's with more 1's stick out at the points where they differ but stick in at the points where they both have 1's because of the shrinkage, so no two p's are nested. (2) I missed the part where the polygons should all be convex but by choosing the sizes of P, Q, and R more carefully they can be made all convex without affecting the overall construction; I will edit the answer to fix that.  

---

