Largest Volume Inscribed Rectangles in Convex Sets Defined by Finite Number of Inequalities

This paper considers the problem of finding maximum volume (axis-aligned) inscribed boxes in a compact convex set, defined by a finite number of convex inequalities, and presents optimization and geometric approaches for solving them. Several optimization models are developed that can be easily generalized to find other inscribed geometric shapes such as triangles, rhombi, and squares. To find the largest volume axis-aligned inscribed rectangles in the higher dimensions, an interior-point method algorithm is presented and analyzed. For two-dimensional space, a parametrized optimization approach is developed to find the largest area (axis-aligned) inscribed rectangles in convex sets. The optimization approach provides a uniform framework for solving a wide variety of relevant problems. Finally, two computational geometric $(1-\epsilon )$–approximation algorithms with sublinear running times are presented that improve the previous results.

History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms—Continuous.

Funding: The author is grateful for the support of Northeastern University for this research.

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0239) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0239). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.