*Given a convex polygon P, find the largest-area inscribed triangle* is a very classical problem.

It's well known that it can be solved by *rotating calipers* in O(n) complexity.

But this paper said, the technique *rotating calipers* was found to be incorrect.

So confused.

Live a healthy life , stay away from Geometry

You can check for yourself.

I implemented the algorithm from the original paper and it seems like the provided breaking case is valid and breaks it (code, case).

Can you re-post these? It now returns 404, document not found

Is there an O(n^2) algorithm that is easy to implement instead of O(n)? Any code or links would be appreciated.

I even remember coding this problem at the Petrozavodsk camp...

Model solution must have also been wrong lol

Do you have a link to the problem?

Rotating calipers as such is not incorrect. This is the name for a general algorithm design technique (see https://en.wikipedia.org/wiki/Rotating_calipers ) and most algorithms based on the technique are correct.

The thing that is incorrect is one particular application of the technique: Dobkin and Snyder's algorithm for the largest inscribed triangle. The counterexample you linked works, the algorithm isn't correct.

The 1992 paper by Chandran and Mount gives a correct[*] O(n) algorithm for that problem. Their algorithm is also based on the rotating calipers technique, but the details are different.

[*] up to my best knowledge

As is known to all,

rotating calipershas 16 ways of pronunciation in Chinese (because it is written in 4 Chinese characters, each having 2 ways pronunciation).