Maximal expansion of a convex polygon

Question

There is a convex polygon $X$ contained in another polygon $Z$ (which can be non-convex and even have holes). I would like to expand $X$ to a larger convex polygon $Y$ such that:

• $X\subseteq Y\subseteq Z$
• $Y$ is maximal, i.e, there is no other convex polygon $Y'$ such that $Y\subsetneq Y' \subseteq Z$

NOTE: $Y$ does not have to have maximum area; it only has to be maximal.

What is an algorithm for finding such $Y$?

Answer 1

Algorithm. We maintain a set $S$, which is initially a set of vertices of $X$. Let $CH(S)$ be the convex hull of $S$. We want to find $S$ such that $CH(S) \subset Z$ is a maximal polygon.

We first define operation $extend(s,t)$ which

1. Finds a point $x$ on the ray starting from $s$ and going through $t$ such that $CH(S \cup \{x\}) \subset Z$ and $x$ is the farthest from $s$ (i.e. it's the most we can extend the polygon in direction $s \to t$).
2. Add $x$ to $S$.

$extend$ is the only operation we'll use. Therefore, $CH(S) \subset Z$ by construction. We only need to select a sequence of extensions so that $CH(S)$ is maximal.

The algorithm consists of $2$ phases:

1. Let $c$ be any point strictly inside the $X$. For each vertex $v$ of $Z$ (including inner vertices), perform $extend(c, v)$
2. For all edges $(u,v)$ of $CH(S)$, while possible, perform $extend(u,v)$ and $extend(v,u)$.

The following example demonstrates the algorithm (I omit steps which don't modify $S$, but we should try all vertices of $Z$ (including holes' vertices) and all edges of $CH(S)$):

Proof of maximality.

Let $x \in Z$ be a point such that $x \in Z \setminus CH(S)$ and $CH(S \cup \{x\}) \subset Z$. Let $u \in S$ be a vertex s.t. $(u,x)$ is an edge in $CH(S \cup \{x\})$. We can assume that $x$ is arbitrarily close to $u$. It's clear that when $x$ is sufficiently close to $u$, one of two neighbors of $u$ in $CH(S)$ becomes a neighbor of $x$ in $CH(S \cup \{x\})$. We call this neighbor $v$. Let $u'$ be another neighbor of $u$, and $v'$ be another neighbor of $v$.

Since we can't extend $(v', v)$ and $(u',u)$, there must exist a vertex $y$ of polygon $Z$ lying strictly between lines $(v', v)$ and $(u',u)$ (it's cumbersome to explain, but it's kind of obvious). Then line $(c,y)$ either intersects $(u,x)$ or $(v,x)$. Let $z$ be the intersection point. Then this point 1) lies outside of $CH(S)$, 2) lies in $CH(S \cup \{x\})$ and 3) lies on line $(c,y)$. This means that during phase $1$ we didn't fully extend to $y$, contradiction.

Complexity. We first need to estimate the complexity of $extend$. One can do this with a binary search: for a candidate, build a convex hull and check if it lies inside of $Z$. The convex hull can be built in $O(n)$ (since we only need to add one point) and an intersection with $Z$ can be checked in $O(n)$, so the total time is $O(n \log (precision))$. I suspect that it's possible to get rid of binary search and get $O(n)$ or $O(n \log n)$ time.

Now, we need to estimate the number of calls of $extend$. There are $O(n)$ calls of $extend$ in the first phase. In the second phase, each time we successfully perform $extend$ (i.e. the area of $CH(S)$ increases), one of two things happen:

1. A vertex of $CH(S)$ which was not on the boundary of $Z$, now lies on the boundary of $Z$.
2. A vertex of $Z$ which was not on the boundary of $CH(S)$, now lies on the boundary of $Z$.

Since there are $O(n)$ vertices of $Z$ and $CH(S)$ (it can't have more vertices than $Z$), we call $extend$ at most $O(n)$ times.

Therefore, the total running time is $O(n^2 \log (precision))$