4
$\begingroup$

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$?

$\endgroup$
2
  • $\begingroup$ Not a complete solution, but I think you could get quite far by first of all dividing $Z$ into $O(n^2)$ slabs by drawing vertical lines through each endpoint of every line segment. Each slab then consists of a single (part of a) line segment from the original $Z$ at the top, another at the bottom, and 2 vertical line segments. In the case where $X$ is a single point (or just very small), you could find the slab containing it, and extend both left and right from it, making sure, e.g., that the angle of the top line segment can only "ratchet down" as you move right. $\endgroup$ Aug 29 '17 at 23:05
  • $\begingroup$ take all segments in $Z$ which are visible from all points in $X$ (green), and draw the polygon $S$ (blue). (connect where needed) Go through all concave points in $S$ and draw two lines continuing the segments of that angle into $S$. this is a subdivision line. then, combine the subdivisions until you find the largest combination. i.stack.imgur.com/9FAbs.png this works in many cases, but there is an obvious edge case it doesn't cover. $\endgroup$
    – guest
    Oct 2 '17 at 15:43
1
+100
$\begingroup$

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.

enter image description here

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

$\endgroup$
5
  • $\begingroup$ In phase 1, do you also do $extend(c,v)$ on vertices $v$ that are interior vertices of $Z$ (i.e., vertices of holes)? Since in the example it is not shown. Also, do you consider vertices of $Z$ that are not visible from $c$ (e.g. hidden behind walls)? $\endgroup$ Feb 25 at 7:36
  • $\begingroup$ 1) Thanks, yes, fixed. 2) Yes, for all vertices, including holes. Otherwise, it's not true that there is a vertex lying strictly between lines $(v′,v)$ and $(u′,u)$ in proof of maximality (also, intuitively, you do need this, since you can think about exterior as a large hole). $\endgroup$
    – user114966
    Feb 25 at 7:50
  • $\begingroup$ What about vertices of $Z$ that are not visible from $c$? $\endgroup$ Feb 25 at 8:02
  • $\begingroup$ I think they are not needed, but I consider them. It doesn't hurt anyway, $\endgroup$
    – user114966
    Feb 25 at 8:05
  • $\begingroup$ In the bottom-most point 2, "A vertex of Z which was not on the boundary of CH(S), now lies on the boundary of Z." - should it be "...now lies on the boundary of CH(S)"? $\endgroup$ Feb 25 at 10:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.