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.
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 calipers has 16 ways of pronunciation in Chinese (because it is written in 4 Chinese characters, each having 2 ways pronunciation).