### u0qyz1234's blog

By u0qyz1234, history, 7 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

 » 7 years ago, # |   +339 Live a healthy life , stay away from Geometry
 » 7 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).
•  » » 6 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.
 » 7 years ago, # |   +58 I even remember coding this problem at the Petrozavodsk camp...
•  » » 7 years ago, # ^ |   +41 Model solution must have also been wrong lol
•  » » 6 years ago, # ^ |   +8 Do you have a link to the problem?
 » 6 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
 » 2 years 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).
 » 6 months ago, # |   0 It looks Your text to link here... is a such problem. The tests are generated with some kind of random, so I think the standard solutions may based on some randomization, and I have tried so many rotating calipers solutions and all of them got Wrong Answer(see my wa 31 times!). However, my submission 224617648 base on rotating calipers passed all datas. So can someone try to hack this and tell me how to use randomization to solve this problem?