The widely known linear time algorithm for computing the maximum area triangle in a convex polygon was found incorrect by Keikha et. al. [15]. We present an alternative algorithm in this paper. Comparing to the only previously known correct solution, ours is much simpler and more efficient. Moreover, it can be easily extended to compute the minimum area triangle enclosing a convex polygon. Also, our new approach seems powerful in solving other related problems. In addition, in the second part of this paper (Section 4), we extend our algorithm to compute all the generally 3-stable triangles, i.e. those triangles whose corners lie in P 's boundary and whose area cannot be improved through adjusting one corner. This further leads to a new linear time solution for computing the minimum enclosing triangle. We now briefly introduce Chandran and Mount's method. They first define the P-stable triangles (outside P ). All sides of a P-stable triangle must be touched by P . In particular, two of them must have their midpoints touched by P ; these two are called the legs whereas the remaining one is called the base. Moreover, one of the following holds. (1) The base is flush with P (namely, it contains an edge of P ). (2) one of the legs is flush with an edge of P and has as its midpoint a vertex of this edge. Note that if (1) holds, it is said P-anchored. The P-anchored triangles are in fact introduced in [17], where it is proved that they contain all the local minimums of enclosing triangles of P . It is then proved in [22] that all the P-anchored triangles are "interspersing" -if we move the base to the next edge, the midpoints of two legs will both move in clockwise. Then, by using the rotating-caliper technique ([26]) together with some clever algorithmic tricks, [22] enumerates all the P-anchored triangles in linear time and thus find the minimum enclosing triangles. The algorithm is somewhat involved and description is highlighted and so details on implementation is given in [23] . Later, by using some "more involved" (as said in the paper) observations and techniques, [7] managed to enumerate all the P-stable triangles in linear time. Their algorithm is actually a terrific example of the rotating-caliper technique. Moreover, it was proved that by enumerating all the P-stable triangles, one can easily obtain all local maximums of triangles enclosed in P . To sum up, the known algorithm in [7] indeed computes all the maximum area triangles enclosed in P and all the minimum area triangles enclosing P simultaneously. As comparison, our algorithm for computing the maximum area triangles is more directit does not need to consider all those triangles enclosing P at all. Another major difference is that we do not apply the rotating-caliper technique. In the rotating-caliper approach, usually we first determine one object (like a corner) and then maintain the other objects correspondingly. In our approach, briefly we first determine a pair of objects (like two corners) and then maintain the other correspondingly. The difficulty of designing algorithms based on rotating-caliper technique lies in maintaining the corresponding corners efficiently, while our difficulty lies in determining the first pair of objects efficiently. See more in Subsection 1.3. The problems of searching for extremal figures with special properties inside or outside a polygon were initiated in [10, 5, 8] , and have since been studied extensively. The minimum area triangle enclosing a convex polygon can be found in O(n log 2 n) time [17] or even in O(n) time [22] . The minimum perimeter triangle enclosing a convex polygon is solved in O(n) time [4] . The maximum perimeter triangle enclosed by a convex polygon can be solved in O(n log n) time [5] . It is interesting to know whether this can be optimized to linear time. As extended research of finding extremal triangles, [5, 2, 3, 8, 1, 21] studied extremal k-gon (with respect to area or perimeter) inside or outside a convex polygon. In particular, the maximum k-gon can be computed in O(n log n) time when k is a constant. It is interesting to know whether this can be optimized to linear time (by our approach). Another direction is to find maximum area triangles inside a simple polygon [19] . Also, we can ask this type of problems in three dimensional space; pioneer research in this direction are [28, 27] . Instead of k-gon, people care about extremal figures that admit more geometric properties, such as equilateral triangle and squares, rectangles and parallelograms, disks and ellipses.
Later, Jin REF proposed another linear time algorithm for the problem of finding the largest triangle inside a convex polygon.
Maximal Area Triangles in a Convex Polygon
ArXiv
ArXiv
Computer Science Mathematics