Triangle / Circle enclosing a set of points

Question

I have a set of points in 2D. I want to find:

1. the smallest triangle enclosing all the points
2. the smallest circle enclosing all the points.

Are there any algorithm to do so? I came across Convex Hull to fit a convex polygon for a set of points. But I want a circle and triangle.

Thanks in advance

Answer 1

If by smallest you are referring to the area then the following algorithms could be potentially useful.

Triangle

The implementation of a linear (i.e. O(n)) algorithm for computing the minimal area triangle enclosing a given set of points in Euclidean 2D space is described in the following open access scientific note:

O. Parvu and D. Gilbert, Implementation of linear minimum area enclosing triangle algorithm, Computational and Applied Mathematics, Springer, pp. 1–16, November 2014.

This scientific note only provides a detailed description of the algorithms initially introduced in the following paper:

J. O’Rourke, A. Aggarwal, S. Maddila, and M. Baldwin, An optimal algorithm for finding minimal enclosing triangles, Journal of Algorithms, vol. 7, no. 2, pp. 258–269, Jun. 1986.

DISCLAIMER: I am one of the authors of this scientific note.

A C++ implementation of the algorithm is made available at:
https://github.com/IceRage/minimal-area-triangle

and will be included in the next major release (3.0) of OpenCV.

Circle

A minimal area enclosing circle algorithm is described in the following paper:

G. Bernd, Fast and Robust Smallest Enclosing Balls, Proceedings of the 7th Annual European Symposium on Algorithms (ESA), Springer, pp 325-338, 1999.

A C++ implementation of the algorithm is made available at:
http://www.inf.ethz.ch/personal/gaertner/miniball.html.

Answer 2

There are O(n) algorithms for both these problems, but they are non-trivial. See http://en.wikipedia.org/wiki/Smallest-circle_problem and http://prografix.narod.ru/source/orourke1986.pdf. Computing an axis-aligned bounding box, or centring a circle or equilateral triangle on the mean of the co-ordinates of the convex hull would be much easier. This might be a good time to think about what your requirements really are, or to find a library implementation.