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

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

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

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:

• Antipodal points
• The Rotating Calipers: An Efficient, Multipurpose, Computational Tool
• COMPUTATIONAL GEOMETRY WITH THE ROTATING CALIPERS

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:

• Robert Hood
• Fossil in the Ice
• Trash Removal
• Fence Orthogonality

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.

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

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