arbitrary_A's blog

Need help on Rotating Calipers technique
By arbitrary_A, history, 6 years ago, In English

i tried to learn this technique from this blog.. but i couldn't understand it clearly from this mentioned site..so need some good blogs on this! you may also add related problems...

thanks in advance!

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

»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Before you conduct any further research, I have to warn you that the technique was proven wrong in finding the largest triangle in a convex https://codeforces.com/blog/entry/52341.

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

    thanks for your kind information :)

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

    Maybe is wrong for that problem but is useful and proven truth for other problems, like fartest pair of points on a cloud, polygon width, minkowski sum of polygons, convex hull of two convex polygons, etc.

    All this problems turn to be linear with this technique.

    I recently solved a problem of fartest pair of point under other metric using rotating calipers

    But is good to know problems that cannot be solved that way. Thanks

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

      your(cbosch_carlgauss) mentioned problems can't be solved without this way?? i meant alternate solutions except this technique??

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

        Yeah, result that mostly of that problems can be done in O(NlgN) or O(Nlg2(N)) time, but with rotating calipers you can archive O(N) time, assuming convex hull is done.

        It seems not to useful but others solutions depens on binary searches and others things that make the code difficult to implement and rotating calipers take short coding.

        → Reply