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.
Cabello al @cite_0 studied the problem of finding the largest-area or largest-perimeter rectangle that is inscribed in a convex polygon. They presented an exact algorithm that runs in @math time, and a @math -approximation algorithm that runs in @math time; see also @cite_20 @cite_25 @cite_8 @cite_18 . DePano, Ke and O'Rourke @cite_16 studied the problem of computing the largest-area square and equilateral triangle contained in a convex polygon. Jin and Matulel @cite_1 studied the problem of computing the largest-area parallelogram that is inscribed in a convex polygon @math , and presented an @math time algorithm, which is based on the fact that largest-area parallelogram must have all of its corners on the perimeter of @math .
@cite_18 @cite_8 @cite_1 @cite_0 @cite_16 @cite_25 @cite_20
2617996878 2064761827 1977740129 1688647404
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. We provide two algorithms for solving the following problem: Given a rectangle containing n points, compute the largest-area and the largest-perimeter subrectangles with sides parallel to the given rectangle that lie within this rectangle and that do not contain any points in their interior. For finding the largest-area empty rectangle, the first algorithm takes O ( n log 3 n ) time and O ( n ) memory space and it simplifies the algorithm given by Chazelle, Drysdale and Lee which takes O ( n log 3 n ) time but O ( n log n ) storage. The second algorithm for computing the largest-area empty rectangle is more complicated but it only takes O ( n log 2 n ) time and O ( n ) memory space. The two algorithms for computing the largest-area rectangle can be modified to compute the largest-perimeter rectangle in O ( n log 2 n ) and O ( n log n ) time, respectively. Since O( n log n ) is a lower bound on time for computing the largest-perimeter empty rectangle, the second algorithm for computing such a rectangle is optimal within a multiplicative constant. We consider approximation algorithms for the problem of computing an inscribed rectangle having largest area in a convex polygon on n vertices. If the order of the vertices of the polygon is given, we present a randomized algorithm that computes an inscribed rectangle with area at least ([email protected]) times the optimum with probability t in time O([email protected]) for any constant t<1. We further give a deterministic approximation algorithm that computes an inscribed rectangle of area at least ([email protected]) times the optimum in running time O([email protected]^2logn) and show how this running time can be slightly improved. We consider the following geometric optimization problem: find a maximum-area rectangle and a maximum-perimeter rectangle contained in a given convex polygon with n vertices. We give exact algorithms that solve these problems in time O ( n 3 ) . We also give ( 1 - e ) -approximation algorithms that take time O ( e - 1 2 log ? n + e - 3 2 ) .