2019/05/30 by Mehdi Behroozi, Behroozi, Mehdi
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG) #Optimization and Control (math.OC) #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.1905.13246
openalex publication_date 2019/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 axis-aligned inscribed rectangles in the higher dimensions, an interior-point method algorithm is presented and analyzed. For 2-dimensional space, a parametrized optimization approach is developed to find the largest (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 sub-linear running times are presented that improve the previous results.