Does a straight line pass through a group of line segments?

In algorithm design, some seemingly simple problems often evade simple solutions. For such problems, the solution requires the help of specific mathematical tools. Once these tools are employed, there's often a direct path to the solution. Such problems offer a unique opportunity to understand complex and difficult mathematical ideas.

This blog discusses a Computational Geometry problem that evades simple solutions. In solving this problem, the required mathematical ideas will become clear. The problem statement is below.

Vertical line segments transversal problem

Problem statement: Given a set of $n$ vertical line segments $S = \left \{ s_1, s_2, \dots , s_n \right \}$ in the plane, decide, in linear time—that is, in $O(n)$ time—whether there is a straight line that passes through all $n$ line segments or not.

As shown in the figure below, each line segment is described by the following three values:

• x-coordinate $x_i$

• upper y-coordinate $y_i^+$

• lower y-coordinate $y_i^-$

The transversal line of $S$ is the line that passes through all line segments in $S$. The problem asks about the existence of a transversal line of $S$. Other variants of the problem are as follows:

• Find a specific transversal line. For example, the line with the lowest/highest slope.

• Identify all transversal lines of $S$.

This blog will also solve the variants of the problem.

Properties of transversal lines

Let us try to find a transversal line of $S$. Consider the straight line $l$ parameterized by the slope $m$ and y-intercept $-c$:

For $l$ to be a valid transversal of the set $S$, it should pass through all line segments in $S$. For $l$ to pass through a line segment $s_i$, the y-coordinate of the point on $l$ when its x-coordinate is $x_i$ should lie between the limits $y_i^-$ and $y_i^+$. This results in the following two linear conditions on the y-coordinate $y_i = mx_i-c$.

Each line segment in $S$ contributes these conditions. For $l$ to be a valid transversal of $S$, it should satisfy all such conditions.

The conditions are linear constraints in the unknowns $m$ and $c$. The valid transversal lines satisfy all these constraints. We have successfully transformed the problem of finding a transversal line of $S$ into an optimization problem with linear constraints.

Mathematical optimization and linear programming

Mathematical optimization is the abstraction of the problem of finding the best solution among all possible solutions. A mathematical optimization problem has the form

Where $x = (x_1,...,x_n)$ is the optimization variable, $f_0(x)$is the objective function, $f_i(x)$ are the constraint functions, and $b_i$ are the bounds of the constraints. The objective function encodes the preferred solution amongst the possible choices. The optimization algorithm seeks the optimal choice $x_i^*$ for the optimization variable $x$ that minimizes (or maximizes) the objective function, depending on the problem. The choices for $x$ are limited by the constraint functions. The set of all possible choices for $x$ is called the feasible set. It's possible that the constraints are such that the feasible set is empty and in this case, the optimization problem is said to be infeasible.

The difficulty of solving an optimization problem depends on the nature of the objective and the constraint functions. The simplest form of an optimization problem is called a linear program, where the objective and constraint functions are linear.

In the objective function $g^Tx$, the $T$ in the superscript represents the transpose of the column-matrix $g$. Several algorithms can efficiently solve linear programs.

Luckily, the vertical line segment transversal problem maps to a linear program.

Finding transversal line using linear programming

The following linear program checks for the existence of a transversal line.

Here, the optimization variable is $(m, c)$. The constraint function is just the reformatting of the constraints given above, in matrix form. The objective function is irrelevant as we are not looking for any particular transversal line. The existence of the transversal line depends on the constraints.

The objective function $g$ can be used to indicate our preference. For example, to find the transversal line with the maximum gradient, set $g=\begin{bmatrix} -1\\0\end{bmatrix}$.

The optimize.linprog function of Python's SciPy library can be used to solve the problem. The code below returns the optimal value of the optimization variable in case the linear program is feasible. Otherwise, it prints the message The problem is infeasible.

Let us visualize the solution of the problem instance given in the code above. In the figure on the left, the three vertical line segments clearly admit several transversal lines. In the figure on the right, the set of transversal lines are visualized by plotting the feasible set of the constraint functions in the $(m,c)$ plane, which is the configuration space of the linear model. Each vertical line segment $s_i$ restricts the solution by adding two constraints that define the strips in the configuration space, shown in green. The feasible region, shown in blue, is the intersection of all the green strips and describes the set of all valid transversal lines for this instance. The optimal solution is the line with the maximum slope $m$, which is shown on the primal plane as a dashed line and on the dual plane as the right-most feasible point.

The plot on the right depicts what is known as the dual plane. A line $l: y=mx-c$ in the $(x,y)$-plane can be represented as the point $(m,-c)$ in the $(m,c)$-plane. The $(x,y)$-plane is called the primal plane and the $(m,c)$-plane is called the dual plane. The primal-dual transform is a very useful tool in computational geometry, and is used here to visualize the set of valid transversal lines in the solution space. The feasible set (blue region) can be projected back to the primal plane to see the region of the transversal lines.

The problem instance in lines 11–14 is shown below, where there is no transversal line and the green strips don't have a common region of intersection. For this case, the linear program is infeasible and hence the program prints The problem is infeasible .

Visualizing transversal lines in the primal plane

Visualize the set of transversal lines by projecting the feasible region in the dual plane back to the primal plane.

The feasible region is a convex polygon. Each vertex of the convex polygon represents a line in the primal plane. These vertices are projected back to the primal plane as dashed lines and the region in between all pairs of lines is filled to represent the set of transversal lines. There are some examples in the slides below.

The number of dashed lines on the left is equal to the number of vertices of the blue feasible polygon on the right.