Maximum-area triangle in a convex polygon, revisited

Ivor van der Hoog; Vahideh Keikha; Maarten Löffler; Ali Mohades; Jérôme Urhausen

doi:10.1016/j.ipl.2020.105943

Maximum-area triangle in a convex polygon, revisited

Ivor van der Hoog, Vahideh Keikha, Maarten Löffler, Ali Mohades, Jérôme Urhausen

Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Tidsskriftartikel › Forskning › peer review

Abstract

We revisit the following problem: Given a convex polygon P, find the largest-area inscribed triangle. We prove by counterexample that the linear-time algorithm presented in 1979 by Dobkin and Snyder [5] for solving this problem fails, as well as a renewed analysis of the problem. We also provide a counterexample proving that their algorithm fails finding the largest-area inscribed quadrilateral. Combined with the work in [2], [3], it follows that the algorithm is incorrect for all possible values of k.

Originalsprog	Engelsk
Tidsskrift	Inf. Process. Lett.
Vol/bind	161
Udgave nummer	105943
Sider (fra-til)	105943
Antal sider	1
DOI	https://doi.org/10.1016/j.ipl.2020.105943
Status	Udgivet - 5 maj 2020
Udgivet eksternt	Ja

Adgang til dokumentet

10.1016/j.ipl.2020.105943

Citationsformater

@article{31ea4b10d9b14c98a70509522284a7fd,

title = "Maximum-area triangle in a convex polygon, revisited",

abstract = "We revisit the following problem: Given a convex polygon P, find the largest-area inscribed triangle. We prove by counterexample that the linear-time algorithm presented in 1979 by Dobkin and Snyder [5] for solving this problem fails, as well as a renewed analysis of the problem. We also provide a counterexample proving that their algorithm fails finding the largest-area inscribed quadrilateral. Combined with the work in [2], [3], it follows that the algorithm is incorrect for all possible values of k.",

keywords = "Computational geometry, Convex polygon, Largest triangle, Largest 4-gon",

author = "\{van der Hoog\}, Ivor and Vahideh Keikha and Maarten L{\"o}ffler and Ali Mohades and J{\'e}r{\^o}me Urhausen",

year = "2020",

month = may,

day = "5",

doi = "10.1016/j.ipl.2020.105943",

language = "English",

volume = "161",

pages = "105943",

journal = "Inf. Process. Lett.",

issn = "1872-6119",

publisher = "Elsevier",

number = "105943",

}

TY - JOUR

T1 - Maximum-area triangle in a convex polygon, revisited

AU - van der Hoog, Ivor

AU - Keikha, Vahideh

AU - Löffler, Maarten

AU - Mohades, Ali

AU - Urhausen, Jérôme

PY - 2020/5/5

Y1 - 2020/5/5

N2 - We revisit the following problem: Given a convex polygon P, find the largest-area inscribed triangle. We prove by counterexample that the linear-time algorithm presented in 1979 by Dobkin and Snyder [5] for solving this problem fails, as well as a renewed analysis of the problem. We also provide a counterexample proving that their algorithm fails finding the largest-area inscribed quadrilateral. Combined with the work in [2], [3], it follows that the algorithm is incorrect for all possible values of k.

AB - We revisit the following problem: Given a convex polygon P, find the largest-area inscribed triangle. We prove by counterexample that the linear-time algorithm presented in 1979 by Dobkin and Snyder [5] for solving this problem fails, as well as a renewed analysis of the problem. We also provide a counterexample proving that their algorithm fails finding the largest-area inscribed quadrilateral. Combined with the work in [2], [3], it follows that the algorithm is incorrect for all possible values of k.

KW - Computational geometry

KW - Convex polygon

KW - Largest triangle

KW - Largest 4-gon

U2 - 10.1016/j.ipl.2020.105943

DO - 10.1016/j.ipl.2020.105943

M3 - Journal article

SN - 1872-6119

VL - 161

SP - 105943

JO - Inf. Process. Lett.

JF - Inf. Process. Lett.

IS - 105943

ER -

Maximum-area triangle in a convex polygon, revisited

Abstract

Adgang til dokumentet

Fingeraftryk

Citationsformater