In this section we'll analyze the complexities of the algorithms we presented.

**Stabbing lines algorithm:**

* Theorem 1*: The number of edges bordering the stabbing region for n line
segments in the plane is bounded by O(n).

* Proof:* Let W denote an arbitrary
double wedge determined by two lines intersecting at point P. Let's name the half-rays bordering W, which emanate
from P, upper right, upper left, lower left and lower right rays.

Let S denote the stabbing region for n line segments consisting of m convex polygons P1, P2, ... ,Pm, ordered by their projections onto the x-axis. We classify the edges of each polygon by the kind of half-ray supporting them. We prove that each one of the 4 half-ray classes is associated with at most 2n+1 edges.

Let's consider edges associated with upper right rays. Assign to each polygon Pi the list of upper right rays which determine the bordering edges of Pi. Obviously, only the upper right ray with minimal slope in the list for polygon Pi can also determine a bordering edge for a polygon Pj, for j greater than i. Now, remove the upper right rays with minimal slope from m lists. Each upper right ray occurs at most once in these reduced lists. Consequently, the original lists contain at most n half-rays with non-minimal slope and at most m half-rays with minimal slope, respectively.

As m is no more that n+1 and the same argument holds for the remaining 3 types of half-rays, we conclude that 8n+4 is an upper bound for the number of edges.

* Lemma 1:* The intersection of two stabbing regions for n1 and n2 segments can
be computed in O(n1 + n2) time.

**Proof:**** **We have just shown
that total number of edges in both regions is O(n1 + n2). Therefore, total
number of vertices is also linear. Moreover, at each step we can keep all the
vertices sorted. Therefore, by using plane-sweep technique, or some similar one,
for each vertex all the computations required may be performed in constant time.
Therefore, total amount of work required for this merge step is linear.

* Theorem 2:* The stabbing region for n line segments in the plane can be
computed in O( n log n) time.

* Proof:* Follows directly from lemma 1 and our divide-and-conquer strategy. The
time the algorithm requires T(n) = 2*T(n/2) + O(n) = O( n log n).

**Shortest transversals
algorithm:**

* Theorem 3:* The algorithm finds the minimal line segment that
intersect a given set of n line segment is O(n log

** Proof: **The stabbing region can
be found in O(n log n) time complexity (according to theorem 2). In order to
avoid recomputing the envelopes and the convex hulls for every region, we can
make use of the dual plane information of the region and compute the convex
hulls in linear time. Then the "rotating-calipers" can be used in order to find
the critical support line between the convex hulls. The envelopes can also be
efficiently updated by using a balanced tree data structure (see reference [2]
for details). This will allow to reach the total complexity of O(n log