# Inscribing convex polygon within simple polyon

Suppose you are given a simple (but not necessarily convex) polygon $C$ and a point $p$ inside this polygon. I have a particular way of inscribing a convex polygon $I$ within $P$, and I would like to know (a) if this is a known concept from geometry and (b) if there exists an efficient algorithm for computing $I$.

The idea is the following:

1. For each edge of $C$, find the closest point to $p$ on that edge.
2. If the closest point is not an endpoint or is an endpoint that is not a reflex angle, extend the edge into a line.
3. If the closest point is an endpoint $v$ that is a reflex angle, draw a line that passes through $v$ and is orthogonal to the line segment from $p$ to $v$.
4. For each line from (2) and (3), construct the half-plane containing $p$ bounded by that line.
5. $I$ is the polygon created by the intersection of all half-planes from (4).

$I$ will be convex because it is the intersection of half-planes.

For example, in the following figure, the solid black boundary forms $C$, the blue lines are the ones constructed in step (1) orthogonal to the corresponding dotted lines, and the gray region is $I$.

Below is the original construction, which @HSN pointed out was completely incorrect.

Suppose you are given a simple (but not necessarily convex) polygon $C$ and a point $p$ inside this polygon. I have a particular way of inscribing a convex polygon $I$ within $P$, and I would like to know (a) if this is a known concept from geometry and (b) if there exists an efficient algorithm for computing $I$.

The idea is the following:

1. For each vertex $v$ of $C$ that forms a reflex interior angle (between 180 and 360 degrees), draw a line that passes through $v$ and is orthogonal to from $p$ to $v$.
2. For each line from (1), construct the half-plane containing $p$ bounded by that line.
3. $I$ is the polygon created by the intersection of $C$ with all half-planes from (3).

For example, in the following figure, the solid black boundary forms $C$, the blue lines are the ones constructed in step (1) orthogonal to the corresponding dotted lines, and the gray region is $I$.

I'm not convinced this construction actually works for any $p$ and $C$ and I don't think I've come across this particular construction before. Why am I doubtful?

To make things somewhat easier, let's give all vertices in your picture a name. The point at the left-hand bottom is $A$, at the right-hand bottom $B$ and continuing counterclockwise up to $H$. The two vertices having a reflex interior angle are $E$ and $F$. We will elongate the line segment $EF$ and let $S$ be the intersection of this line with $AH$.

Now, look what happens if we choose $p$ inside of the rectangle $SFGH$. The perpendicular to $pE$ through $E$ cuts off a triangle having $ED$ as a side (and a third point on $CD$). When also using the perpendicular to $pF$ through $F$, we also get a trapezoid shape having $EF$ as a side.

I'm not good at quickly making pictures that look alright and don't like using a link that may expire, but the following is a horrible illustration of what I mean. Maybe someone would like to improve it. As you can see, the result consists of two polygons joined at the vertex $E$ and is not convex.

• Sorry, my explanation was very bad. What I meant was that each line passing through a reflex vertex constructs a half-plane containing $p$. Then $I$ is the intersection of all of these half-planes with $P$. I believe that this is convex. I've updated the question with this information. – Daniel Ricketts Jul 8 '16 at 17:35
• Would a more restrictive, use the two nearest vertices remedy this problem? – Andres Mejia Jul 8 '16 at 17:37
• @AndresMejia I don't think that would work because the closest vertex might not be visible from $p$. I think that the edit I made solves the issue, but I could be wrong. – Daniel Ricketts Jul 8 '16 at 20:59
• @BmoreDaniel: I still don't think that works. If we make the right-hand tower a lot higher (that is, elongate $DE$ upward and elongate $BC$ accordingly), then at some point the perpendicular to $pF$ through $F$ will intersect the new version of $DE$, in which case the intersection of $C$ and all half-planes containing $p$ won't even be connected (consisting of the part containg $p$ as it is now and some triangle or quadrilateral originating from the right-hand tower). – HSN Jul 9 '16 at 11:09
• @BmoreDaniel: May I inquire for what reason you're trying to do this? This attempt gives me the impression you're looking for some construction that might actually be done a lot simpler. – HSN Jul 9 '16 at 11:11