Convex polygons inclusion relation

Question

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

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?

Answer 1

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