u0qyz1234's blog

O(n) algorithm for finding largest triangle in a convex is wrong?
By u0qyz1234, history, 7 years ago, In English

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.

  • Vote: I like it
  • +419
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +339 Vote: I do not like it

Live a healthy life , stay away from Geometry

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +70 Vote: I do not like it

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).

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it +58 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +27 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it -60 Vote: I do not like it

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).

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply