Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/10383
Title: | Implementation of linear minimum area enclosing traingle algorithm |
Authors: | Gilbert, D Parvu, O |
Keywords: | Minimum area triangle;Benchmark;Convex polygon;Rotating caliper;Computational geometry |
Issue Date: | 2016 |
Publisher: | Sociedade Brasileira de Matemática Aplicada e Computacional |
Citation: | Computational and Applied Mathematics, 35(2): pp. 423–438, (2016) |
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 10,000 variable sized, randomly generated convex polygons for illustrating the linearity of the algorithm. |
Description: | This article has been made available through the Brunel Open Access Publishing Fund. |
URI: | http://bura.brunel.ac.uk/handle/2438/10383 |
DOI: | http://dx.doi.org/10.1007/s40314-014-0198-8 |
ISSN: | 2238-3603 |
Appears in Collections: | Publications Brunel OA Publishing Fund |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Fulltext.pdf | 1.1 MB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.