A technique for solving the polygon inclusion problems

2017/07/13 by Jin, Kai, Zhu, Taikun, Luo, Ruixi
#Computational Geometry (cs.CG) #FOS: Computer and information sciences #I.3.5

paper · doi:10.48550/arxiv.1707.04071

Abstract

We propose a technique called Rotate-and-Kill for solving the polygon inclusion and circumscribing problems. By applying this technique, we obtain O(n) time algorithms for computing (1) the maximum area triangle in a given n-sided convex polygon P, (2) the minimum area triangle enclosing P, (3) the minimum area triangle enclosing P touching edge-to-edge, i.e. the minimum area triangle that is the intersection of three half-planes out of the n half-planes defining P, and (4) the minimum perimeter triangle enclosing P touching edge-to-edge. Our algorithm for computing the maximum area triangle is simpler than the alternatives given in [Chandran and Mount, IJCGA'92] and [Kallus, arXiv'17]. Our algorithms for computing the minimum area or perimeter triangle enclosing P touching edge-to-edge improve the O(nlog n) or O(nlog²n) time algorithms given in [Boyce et al., STOC'82], [Aggarwal et al., Algorithmica'87], [Aggarwal and J. Park., FOCS'88], [Aggarwal et al., DCG'94], and [Schieber, SODA'95].

Related

• Linear time Minimum Area All-flush Triangles Circumscribing a Convex Polygon
• An algorithm to find maximum area polygons circumscribed about a convex\n polygon
• Max/Min Puzzles in Geometry
• A linear-time algorithm for the maximum-area inscribed triangle in a convex polygon
• On implementation of the minimal perimeter triangle enclosing a convex polygon algorithm