Linear time Minimum Area All-flush Triangles Circumscribing a Convex Polygon

2017/12/14 by Jin, Kai, Huang, Zhiyi
#Computational Geometry (cs.CG) #FOS: Computer and information sciences #I.3.5

paper · doi:10.48550/arxiv.1712.05081

Abstract

We study the problem of computing the minimum area triangle that circumscribes a given n-sided convex polygon touching edge-to-edge. In other words, we compute the minimum area triangle that is the intersection of 3 half-planes out of n half-planes defined by a given convex polygon. Building on the Rotate-and-Kill technique Arxiv:1707.04071, we propose an algorithm that solves the problem in O(n) time, improving the best-known O(nlog n) time algorithms given in [A. Aggarwal et. al. DCG94; B. Schieber. SODA95. Our algorithm computes all the locally minimal area circumscribing triangles touching edge-to-edge.

Related

• A technique for solving the polygon inclusion problems
• A linear-time algorithm for the maximum-area inscribed triangle in a convex polygon
• Minimum-Area Enclosing Triangle with a Fixed Angle
• On implementation of the minimal perimeter triangle enclosing a convex polygon algorithm
• Robust Computation of a Minimum Area Convex Polygon Stabber of a Set of Isothetic Line Segments