2

Suppose I have a star-shaped region in the plane with a particular point marked. The marked vertex is in the kernel of the star. enter image description here

In the image the left most point is marked in blue. Yes I drew this in paint-- don't judge me. Just by looking it would appear that the largest (area) convex region inside this star that has the marked point as a vertex is the following yellow subset: enter image description here

Is there a mathematical way (algorithm) to compute this region? I don't see another way to do it rather than inspection. That is, by sight I can remove the points that stick way out into pointy regions, but I want a way to do this systematically (not by sight) using the coordinates of all the vertices.

amcalde
  • 4,674

1 Answers1

0

This "largest convex region inside this star that has the marked point as a vertex" actually is not a well-defined concept. Imagine a non-convex quadrangle $ABCD$ with left-most vertex $A$ as marked vertex, and a reflex angle at $C$.

How would you define your largest convex region in that case?

Gamow
  • 451
  • 1
    I think, the largest (in terms of area) convex polygon inside a nonconvex polygon is quite clear definition. There is one or two solutions in your quad example. – V-X Feb 05 '16 at 14:49
  • But what is "largest" referring to? Number of vertices? Circumference? Area? Diameter? – Gamow Feb 05 '16 at 14:50
  • I added the word "area" to the post. – amcalde Feb 05 '16 at 14:51