Assume we are given two polygons: P1: a convex polygon. P2: a polygon within P1 (either convex or non-convex)
Now I am looking for a greedy algorithm to find polygon p3 such that P3 is inside P1 and it contains p2. The goal is to minimize the number of edges of P3.
On
Since this will probably be a bit lengthy, a tl;dr: I have a greedy algorithm that finds a solution with at most $1$ extra edge compared to the optimal. Depending on the precise meaning of a "polygon containing another polygon", it could actually be greedy optimal. If someone can prove a stronger statement than the one I use, it would be optimal regardless of what meaning we chose.
Also, because I'm a fairly lazy person, I may make some wild statements without justifying them, in which case feel free to ask for more details.
EDIT: after thinking about things a little more, I realized that part of what I say in the final part (about when this approach could reach optimality or not) is most likely bogus, so I removed it. I'll put a revised version within a day or so.
EDIT2: Revised.
First off, let's agree on what we call polygons. Here I'll consider polygons to be "full" and thus $2$-dimensional, as opposed to just being a $1$-dimensional cycle of line segments. This is similar to the distinction between a ball and a sphere, or in $\mathbb R^2$ between a disk and a circle.
With that said, the statement "a polygon $P$ contains another polygon $Q$" means $Q\subseteq P$. I'll denote the boundary of a polygon $P$ by $\partial P$. It corresponds to the cycle of line segments.
Your task is to find some polygon $P_3$ such that $P_2\subseteq P_3\subseteq P_1$ with minimum number of edges/vertices. Because $P_1$ is convex, we can prove there exists a solution $P_3$ that is convex, and for such a convex solution $P_3$ it is equivalent to contain $P_2$ or its convex hull. So as many remarked, we can assume without loss of generality that $P_2$ is convex.
My approach is similar, yet opposed to what @user7530 suggested. Similar because we reduce to a class of polygons that contains an optimal solution, and is fairly easy to explore. Opposed because the constraint that every edge of the solution $P_3$ must contain a vertex of $P_2$ can be interpreted as shrinking $P_3$ until it touches $P_2$, whereas my approach is rather to enlarge $P_3$ until it touches $P_1$.
I claim the following:
There is an optimal solution $P_3$ such that :
- every vertex of $P_3$ is in the boundary of $P_1$
- at most one edge of $P_3$ does not contain a vertex of $P_2$
To see this just pick any point $x$ in the interior of $P_1$ and consider any optimal solution $P_3$. If $P_3$ has some vertex not on the boundary of $P_1$, simply push it outwards from from $x$ until the vertex lands on the boundary. You obtain a new polygon $\hat P_3\supseteq P_3$ with the same number of edges/vertices. $\hat P_3$ thus satisfies the first condition.
Since $\hat P_3$ has its vertices in the boundary of $P_1$, we can sort them in a clockwise or counter-clockwise order. Pick whichever order you like. Let $x_1,\ldots,x_n$ be the $n$ vertices of $\hat P_3$, sorted in order, and suppose edge $x_1x_2$ does not contain any vertex of $P_2$. We can prove (but I'm lazy) that we can shift $x_2$ along the boundary $\partial P_1$, to a new position $\hat x_2$ (that must be between $x_2$ [inclusive] and $x_3$ [exclusive]) so that segment $x_1\hat x_2$ contains a vertex of $P_2$. We can reiterate for every segment so that $\hat x_i\hat x_{i+1}$ contains a vertex, until we reach $\hat x_n$. At that point, segment $\hat x_nx_1$ may or may not contain a vertex of $P_2$. Either way, all other segments contain a vertex of $P_2$ and my claim is true.
From there, one possible greedy algorithm is to pick some point on $\partial P_1$, then go as far as we can along the boundary, until we make a full turn. One major problem there is that if you select a random starting point, you have no guarantee that you will reach an optimal. (Very) roughly speaking, to have a guarantee of optimality, you would require that you start the greedy procedure from $x_1$.
It is however easy to see that a random starting point gives you a solution polygon $P_3$ with $n$ edges/vertices, and $n\le \text{OPT}+1$, where $\text{OPT}$ is the optimal, minimum number of edges/vertices. Let's continue from our optimal solution with vertices $\hat x_1=x_1,\hat x_2,\ldots,\hat x_n$. Because obviously $n\ge 2$, for any point $y\in\partial P_1$, $y$ is in between two consecutive points $\hat x_i$ and $\hat x_{i+1}$. Because convexity is nice, we can in fact include point $y$ within the polygon. This yields a polygon with $n+1$ edges/vertices, contained in $P_1$ and containing $P_2$. Also, shifting every other vertices again so that they coincide with our "greedy procedure" is free. So picking any random starting point gives you a solution with at most one extra edge/vertex. One obvious choice for a starting point would be any vertex of $P_1$.
If you believe in your luck, you could very well pick some starting point and achieve optimality. If you're not too concerned about time complexity, you could also try out a number of different starting points (say, every vertices of $P_1$, but really any finite subset of $\partial P_1$ is fine) and compare the results. If you get some solution with less edges/vertices, it must be optimal.
Leaving luck aside, if someone can prove that there always exist an optimal solution that contains an arbitrary point $y\in\partial P_1$, then this approach is optimal. Likewise, if someone can prove that there exists an optimal solution that admits a vertex in a finite subset of boundary points (for instance, the vertex set of $P_1$), it suffices to apply this greedy approach to that finite subset to reach an optimal.
There's also an independent criteria that lets you know directly if a given polygon reaches an optimal solution. Say you have a polygon with vertices $x_1,\ldots,x_n\in\partial P_1$, and suppose that for every edge $x_ix_{i+1}$ there exists some point $u$ of $P_2$ in the interior of the edge ($u$ must be distinct from both $x_i$ and $x_{i+1}$). Then I claim that $P_3$ is optimal. If you take any other (optimal or not) solution, you can push its vertices on the boundary $\partial P_1$. Then you can show that for every $i$, it must contain at least one vertex between $x_i$ and $x_{i+1}$ (inclusive-exclusive or exclusive-inclusive).
Now I pretend that there are three main cases that the greedy approach I introduced can encounter. Recall the $\hat x_i$ I introduced earlier. I stopped at $\hat x_n$, but technically nothing prevents us from seeking a point $\hat x_{n+1}$ to replace $x_1$. In fact, we can again replace $\hat x_2$ by some point $\hat x_{n+2}$, etc. Potentially, the replacement point is identical to the point it replaces, but that doesn't matter. We end up with an infinite sequence $\hat x_{kn+i}$, with $1\le i\le n$ and $k\ge 0$. For convenience let's denote those point by $x^k_i$, it is the $k$-th replacement for point $\hat x_i$. Our three cases are as follow.
As a closing remark, I didn't bother defining what I meant by "bounded" or "unbounded", but since this post is already quite lengthy I'll just assume you have an intuitive understanding of it. Not like I proved any of the statements in those three cases so it doesn't really matter.
I have an attempt to the problem. We transform P2 to a convex polygon by connecting the concave parts, let's call it P2' and its number of edges is N. We remark that P2' is inside P1 and contains P2. So P2' verify the conditions. Now we need to find the polygon with the minimum number of edges (between 3 and N). we try to minimize the number of edges of P2' iteratively. there are two ways to do that: linking two edges by adding a point or linking two edges by adding a line. then verify if the new polygon is still in P1, otherwise test the next edges until we test all of them. we stop when we cannot decrease the number anymore.