Finding a minimal width strip which encloses a set of points in the plane

Question

Problem: Consider a set of $n$ points in the plane, how could we find a strip of minimal vertical distance that contains all points?

Definitions: A strip is defined by two parallel lines and the vertical distance is defined as the distance between their intersection points with the $y$ axis.

3 variables solution: In the plane itself, this could be solved using a linear program of three variables, $m$, $a$ and $b$ where we look for $y=m\cdot x+a$ and $y=m\cdot x+b$.

Duality: If we move to the dual plane, we get a set on $n$ lines which can be transformed to $n$ upper half-planes or $n$ bottom half-planes. Denote $C_1$ to be the intersection of all upper half-planes intersection and $C_2$ of the bottom ones. The strip in the dual problem is represented by the two ends of the shortest vertical segment crossing the $C_1$ and $C_2$.

My question is - can we express the problem in the dual plane using a linear program of two variables?

Answer 1

Take the convex hull of your set of points. Then use "rotating calipers" to find the optimal strip. What is needed here to make this work is a lemma that characterizes a potentially optimal solution: Could the optimum occur without one supporting line through two points ("flush" to the hull)?

Added. Yes, that flush-lemma holds, because more-horizontal strips are preferred. So: for each edge $e$ of the convex hull $H$, extend $e$ to a line $L_1$, and let $L_2$ be the parallel line supporting $H$ on the other side. Compute the vertical distance between $L_1$ and $L_2$. Select the shortest distance among all alternatives.