Given a set S of n points in the plane and a fixed angle 0<ω<π, we show how to find in O(nlogn) time all triangles of minimum area with one angle ω that enclose S. We prove that in general, the solution cannot be written without cubic roots. We also prove an Ω(nlogn) lower bound for this problem in the algebraic computation tree model. If the input is a convex n-gon, our algorithm takes Θ(n) time.

Additional Metadata
Keywords Computational geometry, Enclosing problems, Geometric optimization
Persistent URL
Journal Computational Geometry
Bose, P, & De Carufel, J.-L. (Jean-Lou). (2014). Minimum-area enclosing triangle with a fixed angle. Computational Geometry, 47(1), 90–109. doi:10.1016/j.comgeo.2013.07.002