On the Minimum Perimeter Triangle Enclosing a Convex Polygon

摘要

We consider the problem of computing a minimum perimeter triangle enclosing a convex polygon. This problem defied a linear-time solution due to the absence of a property called the interspersing property. This property was crucial in the linear-time solution for the minimum area triangle enclosing a convex polygon. We have discovered a non-trivial interspersing property for the minimum perimeter problem. This resulted in an optimal solution to the minimum perimeter triangle problem.