An Implementation of a linear time algorithm for computing the minimum perimeter triangle enclosing a convex polygon.
Anna Valentinovna. Medvedeva, Asish Kumar Mukhopadhyay · Canadian Conference on Computational Geometry · 2003
In this paper, we discuss an efficient and robust implementation of a linear time algorithm due to [1] for computing the minimum perimeter triangle that circumscribes a convex n-gon. Our implementation is in C++, and utilizes the OpenGL graphics library for visualization and animation. The proposed implementation is efficient in the sense that it complies with the algorithm’s linear time complexity while achieving a small constant factor. The implementation is robust in the sense that it will work for all input instances.