We consider the problem of finding inscribed boxes and axis-aligned inscribed boxes of maximum volume, inside a compact and solid convex set. Our algorithms are capable of solving these two problems in any such set that can be represented with finite number of convex inequalities . For the axis-aligned case, we formulate the problem for higher dimensions and present an exact optimization algorithm which solves the problem in \mathcal{O(d^3+d^2n) time, where d is the dimension and n is the number of inequalities defining the convex set. For the general case, after formulating the problem for higher dimensions we investigate the traditional 2-dimensional problem, which is in the literature merely considered for convex polygons, for a broad range of convex sets. We first present a new exact algorithm that finds the largest inscribed axis-aligned rectangle in such convex sets for any given direction of axes in O(n) time. Using this exact algorithm as a subroutine, we present an \epsilon-approximation algorithm that computes (1-\epsilon)-approximation to the largest inscribed rectangle with computational complexity of O(\epsilon^{-1}n)}  . Finally, we show that how this running time can be improved to \mathcal{O(\epsilon^{-1}\log n) with a O(\epsilon^{-1}n) pre-processing time when the convex set is a polygon}  .
This paper considers the problem of finding maximum volume ( axis-aligned ) inscribed parallelotopes and boxes in a compact convex set, defined by a finite number of convex inequalities , and presents an optimization approach for solving them. Several optimization models are developed that can be easily generalized to find other inscribed geometric shapes such as triangles, rhombi, and tetrahedrons. To find the largest axis-aligned (d^3+d^2n) time, where d is the dimension and n is the number of inequalities defining the convex set. For the general case, after formulating the problem for higher dimensions we investigate the traditional 2-dimensional problem, which is in the literature merely considered for convex polygons, for a broad range of convex sets. We first present a new exact algorithm that finds the largest inscribed axis-aligned rectangle in such convex sets for any given direction of axes in O(n) time. Using this exact algorithm as a subroutine, we present an \epsilon-approximation algorithm that computes (1-\epsilon)-approximation to the largest inscribed rectangle with computational complexity of O(\epsilon^{-1}n)} inscribed rectangles in the higher dimensions, an interior-point method algorithm is presented and analyzed . Finally, (\epsilon^{-1}\log n) with a O(\epsilon^{-1}n) pre-processing time when the convex set is a polygon} a parametrized optimization approach is developed to find the largest (axis-aligned) inscribed rectangles in two-dimensional space .
R
We consider
This paper considers
R
inscribed boxes and
maximum volume (
R
inscribed boxes of maximum volume, inside a compact and solid convex set. Our algorithms are capable of solving these two problems in any such set that can be represented with
) inscribed parallelotopes and boxes in a compact convex set, defined by a
R
. For the
, and presents an optimization approach for solving them. Several optimization models are developed that can be easily generalized to find other inscribed geometric shapes such as triangles, rhombi, and tetrahedrons. To find the largest
D
case, we formulate the problem for higher dimensions and present an exact optimization algorithm which solves the problem in \mathcal{O
A
inscribed rectangles in the higher dimensions, an interior-point method algorithm is presented and analyzed
D
we show that how this running time can be improved to \mathcal{O
A
a parametrized optimization approach is developed to find the largest (axis-aligned) inscribed rectangles in two-dimensional space