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

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

Russianlanguage.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'll try thanks.

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:

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.

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

Googling the title gives this page. Can you open the PDF from there?

Yes, I can. Thanks.

Auto comment: topic has been updated by bekar13 (previous revision, new revision, compare).Can we use the intuitive two pointers technique for finding antipodal pairs in convex polygon? Like:

(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

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.

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.

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