Please use this identifier to cite or link to this item: http://buratest.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 SizeFormat 
Fulltext.pdf1.1 MBAdobe PDFView/Open


Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.