## An 'Inside' Bounding Box?

### An 'Inside' Bounding Box?

Hi,

Does anybody know of a way to find the largest quadrilateral
area that will fit _inside_ a given polygon?  the polygon may be
concave, but simple.  preferably, the quadrilateral area is
rectangular. ( so that the solution is not simply to look for
four extreme concavities and join them).

any ideas, or references to algorithms,
code, etc. would be most gratifying.

thanks en avance.

--

==================================================================
Kumar Chalasani   (612)-906-2222

------------------- In Brahms I Trust-------------

### An 'Inside' Bounding Box?

>Hi,

>Does anybody know of a way to find the largest quadrilateral
>area that will fit _inside_ a given polygon?  the polygon may be
>concave, but simple.  preferably, the quadrilateral area is
>rectangular. ( so that the solution is not simply to look for
>four extreme concavities and join them).

There has been quite a bit of work on finding largest inscribed
rectangles, with the orientation of the rectangle prescribed.
See below for one recent reference.  I cannot find a citation
for the case where rotation is permitted, but there also has been
some work on this.  It is a difficult problem, and there is no
easy solution.

, author =      "K. Daniels and V. Milenkovic and D. Roth"
, title =       "Finding the maximum area axis-parallel rectangle in a polygon"
, booktitle =   "Proc. 5th Canad. Conf. Comput. Geom."
, year =        1993
, pages =       "322--327"
Quote:}

We think we need some way of moving the Bounding Box on the page.