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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Nandakumar R
    Commented Aug 2, 2023 at 10:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .