1
$\begingroup$

This post is the inside-out variant of On smallest convex m-gons that contain a given n-gon where m<n

  1. Given a convex n-gon region P, and an m less than n, how to find the max area convex m-gon Q contained within P?

  2. Same question as above with 'perimeter' replacing 'area'.

A natural approach for both questions would be to select m from among the n vertices of P and to connect them with edges into a convex polygon - and repeat for all such m-subsets. Not sure how close to optimal the answer would be (the method itself looks inefficient).

As special cases, one can try to characterize and find the least area/perimeter triangles and convex quadrilaterals that are contained within P.

$\endgroup$

1 Answer 1

2
$\begingroup$

The maximum area inscribed convex $m$-gon can always be found on the vertices. To do this, just consider moving one vertex at a time; we gain area the further we move this point from the diagonal connecting the two vertices adjacent to it. Maximizing distance from this diagonal involves finding the extremum of a linear function within the convex $n$-gon, which is always attained at a vertex.

I suspect you can make a similar argument for the perimeter case, by thinking about the equi-perimeter ellipses and where those would first meet the $n$-gon.

$\endgroup$
1
  • $\begingroup$ Thanks. assuming for both questions, the 'lemma' that one needs only to choose m vertices from the vertices of the given n-gon is valid, can one formulate an algorithm that is polynomial time? A naive algorithm will need to compare nCm candidate m-gons and that seems expensive - even to find maximal inscribed triangle, we would need O(n^3) time. $\endgroup$ Commented Aug 2, 2023 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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