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²  n) time.

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²  n ).