### u0qyz1234's blog

By u0qyz1234, history, 5 years ago,

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.

• +419

 » 5 years ago, # |   +339 Live a healthy life , stay away from Geometry
 » 5 years ago, # | ← Rev. 2 →   +70 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).
•  » » 4 years ago, # ^ |   +16 Can you re-post these? It now returns 404, document not foundIs there an O(n^2) algorithm that is easy to implement instead of O(n)? Any code or links would be appreciated.
 » 5 years ago, # |   +58 I even remember coding this problem at the Petrozavodsk camp...
•  » » 5 years ago, # ^ |   +41 Model solution must have also been wrong lol
•  » » 4 years ago, # ^ |   +8 Do you have a link to the problem?
 » 4 years ago, # | ← Rev. 2 →   +27 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
 » 7 weeks ago, # |   -60 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).