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

Mehdi Behroozi ()
Additional contact information
Mehdi Behroozi: Department of Mechanical and Industrial Engineering, Northeastern University, Boston, Massachusetts 02115

INFORMS Journal on Computing, 2024, vol. 36, issue 3, 787-819

Abstract: 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 − ε ) –approximation algorithms with sublinear running times are presented that improve the previous results.

Keywords: geometric optimization; computational geometry; convex analysis; approximation algorithms; maximum volume inscribed box; inner and outer shape approximation (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0239 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:3:p:787-819

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().