Unimodality of the philon's Line

The following result was proved by G. Toussaint and B. Bhattacharya in 1990. They needed to prove this result in a paper on the shortest transversals. This problem consist of computing the shortest line segment that intersects a set of n given line segments or lines in the plane.

Let QOR be the angle in consideration, P the point we are interested in and let H be the intercept of the philon line on OQ and K be the intercept of the philon line on OR. Let  be the angle subtended by RKH as in Fig. 1. And let l denote the length of line segment HK. Let l() denote l as a function of  where  = <=< . Then l() is a unimodal function on the interval.

Figure 1.  Illustrating the fundamental geometric minimization problem

Figure 2.  Illustrating the proof of the lemma.  O represents the origin and x = u + u'

In order to simplify analysis it is convenient to break up the problem into two cases depending on whether  is greater than  / 2 or not, and to parameterize the problem not as a function of  as in Fig 1, but rather as a function of x =u + u' as in Fig. 2. It is straightforward to demonstrate that unimodality under the first parameterization implies unimodality under the second. Furthermore, we restrict our analysis to the more difficult case of  greater than  / 2. The analysis for  less than or equal to  / 2 is similar and less involved. Accordingly, let p(,ß) be the point in the interior of the cone in question. Thus ß > 0. H'p has length a and is parallel to OK. K'p is parallel to OH. Let l(x) denote the length of line segment HK as a function of x. We then have the following lemma.

Lemma: For x > u > 0, l(x)is a unimodal function.

Proof:Without loss of generality we assume that  > 0. For otherwise we may construct a symmetrical diagram where ß represents the perpendicular drop from p to OH rather than OK. First we determine the value of x such that HK is a minimum.

Since pHH' and pK'K are similar it follows that pH / a = pK / (x - u) and thus, (pH+ pK) / pK = 1+ a / (x - u). Since l(x) = pH+ pK we can write l(x) as follows:

l(x)=(1+a/(x - u)) (1)

Differentiating (1) with respect to x we obtain,

l'(x)=[- 2u+ (- au)x - a].

Since x > u it follows that l'(x)=0 implies that

x3- 2ux2+ (- au)x - a= 0         (2)

Rewriting (2) in standard form we have that

x3+ ax2+ bx + c = 0

where a = -2u < 0; b = u(u - a) < 0, since a > u, and c = -a < 0.

Let , and be roots of (2). We assume that , and  are all real. Then we can write

x3+ ax2+ bx + c = (x -r1)(x - r2)(x - r3)       (3)

We now show that we need only examine one root in more detail. Since a, b, and c, are all less than zero we argue that precisely one of the roots must be greater than zero and the other two must be less than zero. We start by rewriting (3) as follows:

x3+ ax2+ bx + c = x3- ( r1+ r2+ r3)x2+ (r1r2 + r2r3 + r3r1)x - r1r2r3= 0

where a = -( r1+ r2+ r3), b = (r1r2 + r2r3 + r3r1) and c= - r1r2r3. Now c < 0 and the only way - r1r2r3< 0 is for either all three roots to be positive or one to be positive and the other two negative. In addition since b < 0 we must have (r1r2 + r2r3 + r3r1) < 0. Thus consider the case in which all three roots are positive. This implies (r1r2 + r2r3 + r3r1) > 0, a contradiction. It follows that one root must be positive and the other two negative. We can in a similar way show that when only one root of (2) is real that root has to be a positive one. For assume that we have, as before,

x3+ ax2+ bx + c = 0 with a,b,c < 0,

and that we have two complex roots and one real. Let r1be the real root. Then we can rewrite this equation as

(x -r1)(x2+ ex + f ) = 0.

For there to be two complex roots we must have e2- f4 < 0, which implies in turn that f > 0.

Since c = -r1f < 0 and f > 0 it follows that r1> 0.

We conclude from the above discussion that we need only be concerned with the positive root. Let x = r be positive root of (2). We now show that l(x) attains a minimum value at x = r. We do this by demonstrating that the second derivative of l(x) evaluated at x = r must be greater than zero.

Let A = . Then l'(x) =A. It is sufficient to show that dA/dx > 0 at x = r. We see that

dA/dx = 3x2- 4ux + u2 - au (4)

Evaluating (4) at x = r we obtain

dA/dx(r) = 3r2- 4ur + u2 - au
= (2r2- 2ur) + (r2 - 2ur + (u2- au))
= (2r2- 2ur) + a/r, since r3- 2ur2+ (u2- au)r - a= 0.
= 2r(r - u) +a/r. (5)

Since all term in (5) are positive and r > u, dA/dx at x = r > 0, and l(x) attains its minimum value at x = r. Since this minimum is the only local minimum in the region of interest, unimodality in the region of interest follows.