text: 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 @math time, where @math is the dimension and @math 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 @math time. Using this exact algorithm as a subroutine, we present an @math -approximation algorithm that computes @math -approximation to the largest inscribed rectangle with computational complexity of @math . Finally, we show that how this running time can be improved to @math with a @math pre-processing time when the convex set is a polygon.
  @cite_33: We propose a novel geometric structure induced by any given convex polygon @math , called @math , which is an arrangement of @math segments, each of which is parallel to an edge of @math , where @math denotes the number of edges of @math . This structure enjoys six simple yet nontrivial properties, which can be derived from two elementary geometric properties -- convexity and parallelism. We then apply @math to solve the geometric optimization problem of computing the parallelogram(s) in @math with the maximum area. We show that the essential nature of the locally maximal area parallelograms is captured by @math and that computing all these parallelograms reduces to answering @math location queries on @math . We answer each of these queries in @math time, and thus obtain an @math time algorithm for this optimization problem. Our algorithm avoids an explicit construction of @math , which would take @math time.
  @cite_7: The widely known linear time algorithm for computing the maximum area triangle in a convex polygon was found incorrect recently by Keikha et. al.(arXiv:1705.11035). We present an alternative algorithm in this paper. Comparing to the only previously known correct solution, ours is much simpler and more efficient. More importantly, our new approach is powerful in solving related problems.
  @cite_3: This work generalizes the classical problem of finding the largest empty rectangle among obstacles in 2D. Given a set P of n points, here a maximal empty rectangle (MER) is defined as a rectangle of arbitrary orientation such that each of its four boundaries contain at least one member of P and the interior of the rectangle is empty. We propose a very simple algorithm based on standard data structure to locate a MER of largest area in the plane. The worst-case time complexity of our algorithm is O(n3). Though the worst-case space complexity is O(n2), it reserves O(n log n) space on an average to maintain the required data structure during the execution of the algorithm.
  @cite_23: We revisit the following problem: Given a convex polygon @math , find the largest-area inscribed triangle. We show by example that the linear-time algorithm presented in 1979 by Dobkin and Snyder for solving this problem fails. We then proceed to show that with a small adaptation, their approach does lead to a quadratic-time algorithm. We also present a more involved @math time divide-and-conquer algorithm. Also we show by example that the algorithm presented in 1979 by Dobkin and Snyder for finding the largest-area @math -gon that is inscribed in a convex polygon fails to find the optimal solution for @math . Finally, we discuss the implications of our discoveries on the literature.
  @cite_5: 
  @cite_31: We consider the problem of finding the maximum area parallelogram (MAP) inside a given convex polygon. Our main result is an algorithm for computing the MAP in an @math -sided polygon in @math time. Achieving this running time requires proving several new structural properties of the MAP. Our algorithm actually computes all the locally maximal area parallelograms (LMAPs). In addition to the algorithm, we prove that the LMAPs interleave each other, thus the number of LMAPs is bounded by @math . We discuss applications of our result to, among others, the problem of computing the maximum area centrally-symmetric convex body (MAC) inside a convex polygon, and the simplest case of the Heilbronn Triangle Problem.
  @cite_25: Problems concerned with finding inscribing or circumscribing polygons that maximize some measurement are considered such as: Find an area maximizing triangle inscribed in a given convex polygon. Algorithms solving a number of these problems in linear time are presented. They use the common approach of finding an initial solution with respect to a fixed bounding point and then iteratively transforming this solution into a new solution with respect to a new point. The generality of this approach is discussed and several open problems are noted.
summary: Finding largest inscribed objects inside a polygon is not restricted to neither rectangles nor convex polygons. @cite_5 presented @math algorithms for finding inscribed equilateral triangle and square of maximum area inside a convex polygon and an @math algorithm for finding the largest inscribed equilateral triangle inside a general polygon. @cite_3 developed an @math algorithm for the problem of finding the largest empty rectangle among a point set. Jin proposed an @math algorithm @cite_31 and an @math algorithm @cite_33 for finding all locally maximal area parallelogram inside a convex polygon. Recently, @cite_23 showed that a long lasting linear time algorithm for finding the maximal triangle inside a convex polygon proposed in 1979 by Dobkin and Snyder back @cite_25 was in fact incorrect and then provided an @math algorithm for this problem. Later, Jin @cite_7 proposed another linear time algorithm for the problem of finding the largest triangle inside a convex polygon.