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

Research output: Journal Article or Conference Article in Journal › Journal article › Research › 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.

Original language	English
Journal	Inf. Process. Lett.
Volume	161
Issue number	105943
Pages (from-to)	105943
Number of pages	1
DOIs	https://doi.org/10.1016/j.ipl.2020.105943
Publication status	Published - 5 May 2020
Externally published	Yes

Keywords

Computational geometry
Convex polygon
Largest triangle
Largest 4-gon

Access to Document

10.1016/j.ipl.2020.105943

Cite this

@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

Keywords

Access to Document

Fingerprint

Cite this