We already know how to find a stabbing line, or a transversal of a line
segments set. In this section we'll learn how to compute the ** shortest**
such transversal. Note that this topic is rather complicated and could be a
subject to a project all by itself. Therefore, here only a simplified version is
presented.

Let S = { S1, S2, ..., Sn} be a set of line segments and L be its stabbing line (transversal). We'll assume L is not vertical.

Let a(Si , L) denote the end point of Si which lies * above* L, and b(Si, L) --
end point which lies

In figure 1, a(S1, L) = P1; b(S2, L) = Q2.

Also, let A(S, L) = { a(S1, L), a(S2, L), ... a(Sn, L) }, and similarly B(S, L) = { b(S1, L), b(S2, L), ... b(Sn, L) }.

In the figure, A(S, L) = {P1, P2, P3}, B(S, L) = {Q1, Q2, Q3}.

We'll call two transversals L1, L2 * equivalent* if A(S1, L) =
A(S2, L).

Definitions:

1) A simple polygon is a ** kite-shaped** if it contains only
four convex vertices labeled A, B, C, D such that the diagonals [A, C] and [B,
D] lie in the polygon.

Pay attention that AB, BC, CD and DA are * concave chains*.

2) A line segment Si is * left* of another line segment Sj with
respect to a transversal L, if the intersection of Si with L lies to the

The * right* relation is defined in the same manner.

3) * Left-envelope* of a set of line segments S is defined with
respect to an equivalence class of transversals. It's the union of all points P
which are the leftmost intersection points of a line segment in S with some
transversal belonging to the class.

The * right-envelope* is defined similarly.

Let CH(A(S, L)) denote the * convex hull* of the set of points
A(S, L), and CH(B(S, L)) -- the convex hull of B(S, L).

Now we are ready to present an * algorithm*
for computing the shortest transversals:

We are given a set S = {S1, S2, ..., Sn} of line segments.

- Transform each line segment in S into a double wedge in the dual plane (Si --> Ri).
- Let R = R1 U R2 U ... U Rn be the intersection of the double wedges. If R is empty then exit -- no transversal exists.

A(S, L(R_{i+1 })) = { A(S, L(R_{i
})) - a(Sk, L(R_{i })) } U { b(Sk, L(R_{i })) }, and

B(S, L(R_{i+1 })) = { B(S, L(R_{i
})) - b(Sk, L(R_{i })) } U { a(Sk, L(R_{i })) }.

If R_{i } and R_{i+1} are
disjoint, _{ }the line segments whose end points switch sides from
above or below of L(R_{i }) to below or above of L(R_{i+1 }) are
those whose corresponding double wedge centers lie between regions R_{i}
and R_{i+1}. Therefore, we can compute the sets A and B for L(R_{i+1
}) from those for L(R_{i }).

- For every convex region:

- Compute the left envelope, the right envelope, convex hull of the upper end points of S, convex hull of the lower end points of S.

- Compute the critical lines of support between the two convex hulls and concatenate their relevant portions with the envelopes and convex hull boundaries to obtain a kite-shaped polygon.

- Compute the minimum visible distance between the left and right chains of the polygon.

- Select the smallest distance obtained during the previous step and exit with the line segment that determines this distance.