metal_knight's blog

Rotating calipers technique and applications
By metal_knight, history, 8 years ago, In English

Recently I've read about rotating calipers technique and it's applications from wikipedia. I wonder if there is any articles or blogs from where I can learn more about rotating calipers. I understand convexhull technique . I've searched at codeforces but couldn't find any valuable resources or blog posts. If you guys have any valuable resources on this topic please share. It'll be great if someone writes a blog about this topic at codeforces. Also we can discuss about problems related to rotating calipers here. Thanks for reading :)

UPD: I just solved Robert Hood from Kattis online judge. After spending almost a week I've understood the process of rotating calipers. It feels really great to learn a new problem solving technique. I recommend everyone to read this book and visit this site (provided by SuprDewd) for umderstanding rotating calipers technique. Here you can find a basic implementation of rotating calipers for finding diameter of a convex polygon. Also don't forget to look at SuprDewd's comment. Thank you all for helping and encouraging me all the time :)

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

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

I've found this but I think it's not enough. Moreover, it's in Russian language.

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

Rotating Calipers is a very useful technique. So it would be really great If we could discuss about the Topic and related problems here.

Following this important thread :)

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

Could you please write a detailed blog on it, if you have learned it well.

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

I studied the technique some months ago. Unfortunately I don't have all the resources I used while learning, but I remember that the following three links were useful:

There are many applications of rotating calipers, but I think the most basic one is to find the diameter of a convex polygon*. Conceptually it's very simple. We put the polygon between the two jaws of a caliper, and tighten. We then rotate the calipers a full circle around the polygon, while keeping the caliper tight at all times. The answer is then the maximum distance between the two jaws at any point during the procedure.

The rotating calipers technique is basically just an "angle-sweep-line" version of this. We have two parallel lines that are on either side of the polygon, representing the jaws of the caliper. Initially we could, for example, let one of the lines touch the leftmost point of the polygon and the other line touch the rightmost point of the polygon, and say they are completely vertical (i.e. at an angle pi/2). We then simulate this procedure by rotating the two lines at the same speed, keeping track of which two points the two lines are touching, and then only stopping at the moments these points change.

This can then be easily generalized to many applications:

  • Minimum rectangle enclosing a convex polygon: Now we have two calipers that are orthogonal to each other, and again we rotate them around the polygon. This corresponds to having four lines in the simulation, i.e. two pairs of parallel lines, which are then orthogonal to each other so that the interior forms a rectangle.
  • Minimum distance between two convex polygons: Now one of the lines touches one of the polygons, and the other line touches the other polygon. Furthermore, we will initially let one of the lines touch the leftmost point of the corresponding polygon, while the other line touches the rightmost point of the corresponding polygon, and again the lines start out vertical.

See the links above for further applications and more detailed explanations.

For some example code you can look at my implementation. I have a class that represents a single jaw of the caliper (i.e. a single line), and then below (commented out) is how I use that class to find the diameter of an arbitrary polygon. Note that the code uses doubles and angles (as that was more intuitive for me at the time), but a more robust implementation would only use integers.

Finally, here are some practice problems:

Would love to hear if others have more problems.

*) Finding the diameter of an arbitrary polygon can be reduced to this problem by first taking the convex hull. The same is true for many other applications.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    Thank you so much SuprDewd. It's a great help. I've found the book named "COMPUTATIONAL GEOMETRY WITH THE ROTATING CALIPERS" written by Pirzadeh, Hormoz just before your reply. That's why I didn't check my blog post to see if anyone place a comment or not. Sorry for the late response. I'm reading the book written by Pirzadeh, Hormoz now. Hopefully I'll understand the technique soon and will be able to solve some problems related to it. Thanks again.

    PS: If you have enough time you can add those resources at here. It will be easy to find for the future problem solvers.

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

    The link SuprDewd gave for COMPUTATIONAL GEOMETRY WITH THE ROTATING CALIPERS is not working anymore. Can someone please provide the pdf ( I assume it was a link to a pdf) of the link ?

    And thanks SuprDewd, I learnt a lot of things from the links you provided.

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

Auto comment: topic has been updated by rumman_sust (previous revision, new revision, compare).

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

Can we use the intuitive two pointers technique for finding antipodal pairs in convex polygon? Like:

j<-0
for i in [0,n):
     while distance(p[j+1], p[i]) >= distance(p[j+1], p[i]) and j < i:
         if distance(p[j+1], p[I]) == distance(p[j+1], p[I]):
            store (p[I],p[j+1]) in cache
         else:
            clean cache
         j += 1
         yield points in cache

(obviously all incrementation done modulo n)

It worked on Robin Hood, but it fells like it has too simple tests. Any pitfalls? Thank you!

UPD: Both implementations for robin hood are given here

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

    There is a negative example from this Chinese blog

    The O point won't find it's antipodal point A because the of the B point. It may stuck on the C point.

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

      Isn't that true, that the diameter of the figure on the set equals to the distance between point A and that unnamed point between O and C? If yes (and it seems to be like that), the "wrong" algorithm would actually find the correct answer, and it don't need the length of segment "OA" at all.

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

        Yes, I think you're right. But I thought the figure show that you can't find the antipodal point using the binary search approach. For the global diameter, we should find another negative example :)

        → Reply