# Minimum area enclosing triangle algorithm implementation

## Related publication

Ovidiu Pârvu and David Gilbert, Implementation of linear minimum area enclosing triangle algorithm, Computational and Applied Mathematics, Springer, pp. 1–16, November 2014 (Open Access)

## Abstract

An algorithm which computes the minimum area triangle enclosing a convex polygon in linear time already exists in the literature. The paper describing the algorithm also proves that the provided solution is optimal and a lower complexity sequential algorithm cannot exist. However, only a high-level description of the algorithm was provided, making the implementation difficult to reproduce. The present note aims to contribute to the field by providing a detailed description of the algorithm which is easy to implement and reproduce, and a benchmark comprising 10000 variable sized, randomly generated convex polygons for illustrating the linearity of the algorithm.

## Simple usage example

The video below illustrates the step by step execution of the algorithm for a convex 5-gon.

## Benchmark

### Description

The benchmark was created for assessing the efficiency of the algorithm and comprises convex n-gons generated randomly using the Computational Geometry Algorithms Library (CGAL). The value of n ranges from 100 to 10000 with a step size of 100. For each value of n 100 random n-gons were generated. Thus the total number of convex n-gons in the data set is 10000.

A txt file with the name `benchmark_<number_of_points>_<unique_id>.txt` corresponds to each n-gon. These files have the following format:

• First line contains the number of points defining the convex n-gon;
• The next n lines contain the coordinates of the points: `<point_x_coordinate> <point_y_coordinate>`;
• The last line is blank.

An example of a txt file describing a convex 5-gon is given below:

 `benchmark_5_1.txt` ``` 5 300 700 400 480 643 200 800 1100 1202 1005 ```