How to find minimum possible projection of a polygon on X axis, after rotating at an arbitrary angle?

Question

Given the vertices of a 2D polygon, I have to find the minimum possible projection of the polygon on X axis.

I am allowed to rotate the polygon at arbitrary angle.

At first I thought for the minimum case, at least one of the polygon's sides will be aligned to the X axis, which is not true.

The polygon can be concave or convex.

Answer 1

What you are looking for is called the "Rotating Calipers Algorithm".

https://en.wikipedia.org/wiki/Rotating_calipers

The Wikipedia page about this algorithm has even pseudo-code for your problem.

https://en.wikipedia.org/wiki/Rotating_calipers#Minimum_width_of_a_convex_polygon