0
$\begingroup$

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

Inscribed Polygon

$\endgroup$
0
$\begingroup$

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.

Inscribed Polygon

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Daniel Ricketts Jul 8 '16 at 17:35
  • $\begingroup$ Would a more restrictive, use the two nearest vertices remedy this problem? $\endgroup$ – Andres Mejia Jul 8 '16 at 17:37
  • $\begingroup$ @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. $\endgroup$ – Daniel Ricketts Jul 8 '16 at 20:59
  • $\begingroup$ @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). $\endgroup$ – HSN Jul 9 '16 at 11:09
  • $\begingroup$ @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. $\endgroup$ – HSN Jul 9 '16 at 11:11

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.