Блог пользователя arbitrary_A

Need help on Rotating Calipers technique
Автор arbitrary_A, история, 6 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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://mirror.codeforces.com/blog/entry/52341.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    thanks for your kind information :)

    → Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить