4
$\begingroup$

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?

Improve this question
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ @Elisha: I realize I haven't answered your direct question, but I don't see much need to switch to the dual. $\endgroup$ – Joseph O'Rourke Jul 18 '16 at 16:19
  • $\begingroup$ Thanks. I hoped to have a solution that solves the problem in expected linear time given the points in any order. I guess that this solution requires a convex hull or pre-sorting of the points, so the complexity is n*logn. The rotating calipers is a new view of the problem, and it is very helpful. $\endgroup$ – Elisha Jul 19 '16 at 4:34
  • $\begingroup$ @Elisha: It would be difficult to beat $O(n \log n)$. I believe one could prove a lower bound of $\Omega(n \log n)$. $\endgroup$ – Joseph O'Rourke Jul 19 '16 at 10:38
  • $\begingroup$ Yap, that's true - cs.stackexchange.com/questions/6369/lower-bound-for-convex-hull. I was hoping to avoid the convex hull and reach directly to the strip through the dual plane, but that seems to be a problem. $\endgroup$ – Elisha Jul 20 '16 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.