Finding a Transversal Line for Line Segments in General Position

A transversal line of a set of line segments in a plane is a straight line that passes through all the line segments.

In the first blog post of this series, we solved the vertical line segment transversal problem. Here, we briefly summarize the problem and the method used to solve it, before moving to the next problem in this series.

A Recap of the Vertical Line Segments Transversal Problem#

Problem statement: For a set of $n$ vertical line segments in the plane, decide in $O(n)$ time, whether there is a straight line that passes through all $n$ line segments or not. If such transversal lines exist, then find all of them. Here is one problem instance that admits several transversal lines, two of which are shown.

We mapped the vertical line segment transversal problem to a linear program and solved it using SciPy's optimize.linprog function.

In case the line segments are not confined to be vertical but can take any orientation, the problem becomes trickier, as it is unclear how to formulate it as a linear program. To solve it, we take help from a powerful tool from computational geometry: the concept of duality. Before going into the details of duality, let's see the line segment transversal problem in its general setting.

Line Segment Transversal in General Position #

Problem statement: For a set of $n$ (possibly intersecting) line segments in the plane, decide in $O(n^2)$ time, whether there is a straight line that passes through all $n$ line segments or not. If such transversal lines exist, then find all of them.

To solve this problem, we use duality transforms.

Introduction to Duality Transforms#

A point and a line lying in a plane have two parameters. A point is characterized by its $x$-coordinate and $y$-coordinate and a line by its slope and $y$-intercept. As a point and a line both need two parameters, they can be mapped onto one another.

Consider a line $l: y=ax-b$ in the plane with slope $a$ and $y$-intercept $-b$. This line $l$ can be represented as the point $(a, b)$ in another plane. To differentiate between the two planes, the former is called the primal plane and the latter is called the dual plane. Such mappings are called duality transforms and the image of an object that is transformed is called its dual.

Interesting relations emerge between geometric objects in the primal plane and their transforms in the dual plane. Let's look at the two basic relations.

• By definition, the dual of a line $l: y=ax-b$ is the point $l^* = (a,b)$.

• The dual of a point $p = (c,d)$ is the line $p^* : y = cx - d$.

As shown above, the lines $l_1, l_2, l_3$ in the primal plane intersect at the same point, $p = (c,d)$. Interestingly, the points that are the dual transforms of the three lines, denoted as $l_1^*, l_2^*, l_3^*$, are collinear. Let's see how. The three lines and their duals are as follows:

As the three lines pass through the point $p = (c,d)$, the following equations hold:

We can rearrange the equations as follows:

Concluding that in the dual plane, the points $l_1^*, l_2^*, l_3^*$ lie on the line $y = cx - d$. This is the line $p^*$ which is the dual of the point $p$.

Next, we'll look at the properties of dual transform. We will use some of these properties to derive the dual transform of a line segment.

Properties of Dual Transform#

Let $p$ be a point in the primal plane and $l$ be a line in the primal plane. Let the dual of $p$ be the line $p^*$ and the dual of $l$ be the point $l^*$.

Incidence preservation: The duality transform preserves incidence. In the primal plane, $p$ lies on $l$ if and only if in the dual plane $l^*$ lies on $p^*$. This is illustrated below:

It is easy to see why this is true. Let $p = (a,b)$ and $l: y = cx - d$. As $p$ lies on $l$, the following holds:

The equation above can be rearranged as below:

This indicates that the dual of line $l$, which is the point $l^* = (c,d)$, lies on the line $p^* : y = ax - b$.

Note: The collinearity of dual points of lines that have a common point of intersection is a direct consequence of incidence preservation.

Order preservation: The duality transform preserves order. The point $p$ lies above the line $l$, if and only if, the point $l^*$ lies above the line $p^*$.

Consider a point $p = (a,b)$ that lies above a line $l: y = cx - d$. The following inequality holds:

The inequality relation above can be rearranged as follows:

This proves that the dual of line $l$, which is the point $l^* = (c,d)$, lies above the line $p^* : y = ax - b$.

Dual Transform of a Line Segment#

A line segment $s = \overline{pq}$ is characterized by its two end-points $p$ and $q$. Considering $s$ as a union of infinite points, $s^*$ is the union of the dual lines of these points. As all the points on a line segment are collinear, all the lines in $s^*$ intersect at the same point.

In the dual plane in the figure above, the dual lines $p^*$ and $q^*$ are shown. These lines divide the plane into two double wedges, where a double wedge is the region bounded by two lines. The rest of the lines, which are the duals of the internal points on the line segment $s$, lie in one of the double wedges.

To decide which of the double wedges corresponds to $s^*$, consider how the slope of the dual line varies as we move from $p$ to $q$. The slope starts at $-1$ for the line $p^*$ and increases to $+1$ for the line $q^*$. In general, the slope continuously increases from the left endpoint to the right one. Therefore, the left-right double wedge, shown in gray color, is the region of $s^*$.

The dual of a line segment is the left-right double wedge defined by the dual lines of its endpoints.

Region of Overlap of Dual Transforms of Line Segments#

In the dual plane, a point that lies within the double wedge corresponding to $s^*$ corresponds to a line in the primal plane that intersects the line segment $s$. This is shown in the figure below.

This is true because any line that intersects the line segment $s$ is sandwiched between the points $p$ and $q$. By the order-preserving property, its dual point lies in $s^*$. Therefore, the dual transform of a line segment identifies all its transversal lines.

The transversal line of a set of line segments is the overlapping region of their corresponding double wedges in the dual plane. If the line segments do not admit a transversal line, the overlapping region of the corresponding double wedges will be empty.

Let's see some examples:

Finding the Region of Overlap #

Now, we'll discuss the algorithm that finds the region of overlap of all the double wedges or reports that such a region does not exist.

For $n$ line segments in the primal plane, there are $2n$ bounding lines of their corresponding double wedges in the dual plane. These bounding lines partition the plane into several regions.

• In geometry, the subdivision of a plane into several regions by a collection of lines is known as a line arrangement, where each region is known as a face.

• The boundaries of the faces are chains of straight-line edges.

• Some of these chains are closed, defining faces that are convex polygons, and others are open.

The goal is to find a face that lies in all the double wedges in the line arrangement defined by the bounding lines of double wedges.

Here is an example with two double wedges and the corresponding line arrangement. On each face, the number of double wedges that contain it are labeled.

The line arrangement for a collection of $n$ lines can be created in $O(n^2)$using an incremental algorithm that processes one line at a time and updates the line arrangement.

In the line arrangement, each edge $e$ belongs to the boundary of one particular double wedge. We direct an edge from right to left if it belongs to the upper boundary (shown in blue) and left to right if it belongs to the lower boundary (shown in red). This labeling is used to find the number of double wedges that contain each face.

For each face $f$ in the line arrangement, let $C(f)$ denote the number of double edges that contain $f$. As shown in the figure above, for the face $f^*$ that lies below all the bounding lines, $C(f^*) = 0$. Let $below(e)$ and $above(e)$ denote the faces that lie below and above an edge $e$, respectively. Starting from $f^*$, we can find the $C(f)$ for all faces using the following relation.

Starting from a face $f$, if we enter one of its neighboring faces $f'$ such that the edge $e$ between them lies on the lower boundary of a double wedge $s^*$, then $f'$ lies within $s^*$ and $f$ lies outside $s^*$. Therefore, $C(f')$ is one more than $C(f)$. Similarly, if the edge $e$ between the faces lies on the upper boundary of a double wedge $s^*$, then $f'$ lies outside $s^*$ and $f$ lies within $s^*$. Therefore, $C(f')$ is one less than $C(f)$.

Starting from $f^*$ (where $C(f^*) = 0$), we use the relation above to find the $C$ value for its neighboring faces and continue until all faces are covered. If the maximum $C$ for any face is equal to $n$, the line segments admit transversal lines. Otherwise, they do not.