(***********************************************************************
Mathematica-Compatible Notebook
This notebook can be used on any computer system with Mathematica 3.0,
MathReader 3.0, or any compatible application. The data for the notebook
starts with the line of stars above.
To get the notebook into a Mathematica-compatible application, do one of
the following:
* Save the data starting with the line of stars above into a file
with a name ending in .nb, then open the file inside the application;
* Copy the data starting with the line of stars above to the
clipboard, then use the Paste menu command inside the application.
Data for notebooks contains only printable 7-bit ASCII and can be
sent directly in email or through ftp in text mode. Newlines can be
CR, LF or CRLF (Unix, Macintosh or MS-DOS style).
NOTE: If you modify the data for this notebook not in a Mathematica-
compatible application, you must delete the line below containing the
word CacheID, otherwise Mathematica-compatible applications may try to
use invalid cache data.
For more information on notebooks and Mathematica-compatible
applications, contact Wolfram Research:
web: http://www.wolfram.com
email: info@wolfram.com
phone: +1-217-398-0700 (U.S.)
Notebook reader applications are available free of charge from
Wolfram Research.
***********************************************************************)
(*CacheID: 232*)
(*NotebookFileLineBreakTest
NotebookFileLineBreakTest*)
(*NotebookOptionsPosition[ 13711, 429]*)
(*NotebookOutlinePosition[ 14623, 459]*)
(* CellTagsIndexPosition[ 14579, 455]*)
(*WindowFrame->Normal*)
Notebook[{
Cell[TextData[{
StyleBox["\n",
FontFamily->"Times New Roman",
FontSize->10],
StyleBox["Unimodality of the philon's Line\n\n\n\n\n",
FontSize->14,
FontWeight->"Bold",
FontVariations->{"Underline"->True}],
" \n\n\tThe following result was prooved by G. Toussaint and B. \
Bhattacharya in 1990. They needed to prove this result for 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. \
\nLet 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 ",
StyleBox["\[Theta]",
FontFamily->"Symbol"],
" be the angle subtended by RKH as in Fig. 1. And let l denote the length \
of line segment HK. Let l(",
StyleBox["\[Theta]",
FontFamily->"Symbol"],
") denote l as a function of ",
StyleBox["\[Theta]",
FontFamily->"Symbol"],
" where ",
StyleBox["\[Phi]",
FontFamily->"Symbol"],
" =",
Cell[BoxData[
FormBox[
SubscriptBox[
StyleBox["\[Theta]",
FontFamily->"Symbol"], "1"], TraditionalForm]]],
"< ",
StyleBox["\[Theta]",
FontFamily->"Symbol"],
" \[LessSlantEqual] ",
Cell[BoxData[
FormBox[
SubscriptBox[
StyleBox["\[Theta]",
FontFamily->"Symbol"], "2"], TraditionalForm]]],
"< \[Pi]. Then l(",
StyleBox["\[Theta]",
FontFamily->"Symbol"],
") is a unimodal function on the interval.\n \n \tIn order to simplify \
analysis it is convenient to break up the problem into two cases depending on \
wheter ",
StyleBox["\[Phi]",
FontFamily->"Symbol"],
" is greater than \[Pi]/2 or not, and to parameterize the problem not as a \
function of ",
StyleBox["\[Theta]",
FontFamily->"Symbol"],
" 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 \
rerict our analysis to the more difficult case of ",
StyleBox["\[Phi]",
FontFamily->"Symbol"],
" greater thant \[Pi]/2. The analysis for ",
StyleBox["\[Phi]",
FontFamily->"Symbol"],
" less than or equal to \[Pi]/2 is similar and less involved. \
Accordinglly, let p(\[Alpha],\[Beta]) be the point in the interior of the \
cone in question. Thus \[Beta] > 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.\n \t\n ",
StyleBox["Lemma:",
FontWeight->"Bold"],
" For x > u > 0, l(x)is a unimodal function.\n \n ",
StyleBox["Proof: ",
FontSlant->"Italic"],
"Without loss of generality we assume that \[Alpha] > 0. For otherwise we \
may construct a symmetricaldiagram where \[Beta] represents the perpendicular \
drop from p to OH rather than OK. First we determine the value of x such \
that HK is a minimum.\n \n Since \[Angle]pHH' and \[Angle]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:\n \n l(x)=",
Cell[BoxData[
FormBox[
SuperscriptBox[
RowBox[{"(",
RowBox[{
FormBox[\(\[Beta]\^2\),
"TraditionalForm"], "+", " ",
FormBox[\(x\^2\),
"TraditionalForm"]}], ")"}], \(1\/2\)], TraditionalForm]]],
"(1+a/(x - u))\t\t\t(1)\n \n Differetiating (1) with respect to x we \
obtain,\n \n l'(x)=",
Cell[BoxData[
FormBox[
SuperscriptBox[
RowBox[{"(",
RowBox[{
FormBox[\(\[Beta]\^2\),
"TraditionalForm"], "+", " ",
FormBox[\(x\^2\),
"TraditionalForm"]}], ")"}], \(\(-1\)\/2\)],
TraditionalForm]]],
Cell[BoxData[
\(TraditionalForm\`\((x - u)\)\^\(-2\)\)]],
"[",
Cell[BoxData[
\(TraditionalForm\`x\^3\)]],
"- 2u",
Cell[BoxData[
\(TraditionalForm\`x\^2\)]],
"+ (",
Cell[BoxData[
\(TraditionalForm\`u\^2\)]],
"- au)x - a",
Cell[BoxData[
\(TraditionalForm\`\[Beta]\^2\)]],
"].\n \n Since x > u it follows that l'(x)=0 implies that\n \n",
Cell[BoxData[
\(TraditionalForm\`\(\ x\^3\)\)]],
"- 2u",
Cell[BoxData[
\(TraditionalForm\`x\^2\)]],
"+ (",
Cell[BoxData[
\(TraditionalForm\`u\^2\)]],
"- au)x - a",
Cell[BoxData[
\(TraditionalForm\`\[Beta]\^2\)]],
"= 0\t\t\t(2)\n\nwhere a = -2u < 0; b = u(u - a) < 0, since a > u, and c = \
-a",
Cell[BoxData[
\(TraditionalForm\`\[Beta]\^2\)]],
" < 0.\n\nLet ",
Cell[BoxData[
\(TraditionalForm\`r\_1\)]],
", ",
Cell[BoxData[
\(TraditionalForm\`r\_2\)]],
", and ",
Cell[BoxData[
\(TraditionalForm\`r\_3\)]],
"be roots of (2). We assume that ",
Cell[BoxData[
\(TraditionalForm\`r\_1\)]],
", ",
Cell[BoxData[
\(TraditionalForm\`r\_2\)]],
", and ",
Cell[BoxData[
\(TraditionalForm\`r\_3\)]],
" are all real. Then we can write\n\n",
Cell[BoxData[
\(TraditionalForm\`\(\ x\^3\)\)]],
"+ a",
Cell[BoxData[
\(TraditionalForm\`x\^2\)]],
"+ bx + c = (x -",
Cell[BoxData[
\(TraditionalForm\`\(\ r\_1\)\)]],
")(x - ",
Cell[BoxData[
\(TraditionalForm\`r\_2\)]],
")(x - ",
Cell[BoxData[
\(TraditionalForm\`r\_3\)]],
").\t(3)\n\nWe 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:\n\n",
Cell[BoxData[
\(TraditionalForm\`\(\ x\^3\)\)]],
"+ a",
Cell[BoxData[
\(TraditionalForm\`x\^2\)]],
"+ bx + c = ",
Cell[BoxData[
\(TraditionalForm\`x\^3\)]],
"- ( ",
Cell[BoxData[
\(TraditionalForm\`r\_1\)]],
"+ ",
Cell[BoxData[
\(TraditionalForm\`r\_2\)]],
"+ ",
Cell[BoxData[
\(TraditionalForm\`r\_3\)]],
")",
Cell[BoxData[
\(TraditionalForm\`x\^2\)]],
"+ (",
Cell[BoxData[
\(TraditionalForm\`\(r\_1\) r\_2\)]],
" + ",
Cell[BoxData[
\(TraditionalForm\`\(r\_2\) r\_3\)]],
" + ",
Cell[BoxData[
\(TraditionalForm\`\(r\_3\) r\_1\)]],
")x - ",
Cell[BoxData[
\(TraditionalForm\`r\_1\)]],
Cell[BoxData[
\(TraditionalForm\`r\_2\)]],
Cell[BoxData[
FormBox[
FormBox[\(r\_3\),
"TraditionalForm"], TraditionalForm]]],
"= 0\n\nwhere a = -( ",
Cell[BoxData[
\(TraditionalForm\`r\_1\)]],
"+ ",
Cell[BoxData[
\(TraditionalForm\`r\_2\)]],
"+ ",
Cell[BoxData[
\(TraditionalForm\`r\_3\)]],
"), b = (",
Cell[BoxData[
\(TraditionalForm\`\(r\_1\) r\_2\)]],
" + ",
Cell[BoxData[
\(TraditionalForm\`\(r\_2\) r\_3\)]],
" + ",
Cell[BoxData[
\(TraditionalForm\`\(r\_3\) r\_1\)]],
") and c= - ",
Cell[BoxData[
\(TraditionalForm\`r\_1\)]],
Cell[BoxData[
\(TraditionalForm\`r\_2\)]],
Cell[BoxData[
FormBox[
FormBox[\(r\_3\),
"TraditionalForm"], TraditionalForm]]],
". Now c < 0 and the only way - ",
Cell[BoxData[
\(TraditionalForm\`r\_1\)]],
Cell[BoxData[
\(TraditionalForm\`r\_2\)]],
Cell[BoxData[
FormBox[
FormBox[\(r\_3\),
"TraditionalForm"], TraditionalForm]]],
"< 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 (",
Cell[BoxData[
\(TraditionalForm\`\(r\_1\) r\_2\)]],
" + ",
Cell[BoxData[
\(TraditionalForm\`\(r\_2\) r\_3\)]],
" + ",
Cell[BoxData[
\(TraditionalForm\`\(r\_3\) r\_1\)]],
") < 0. Thus consider the case in which all three roots are positive. \
This implies (",
Cell[BoxData[
\(TraditionalForm\`\(r\_1\) r\_2\)]],
" + ",
Cell[BoxData[
\(TraditionalForm\`\(r\_2\) r\_3\)]],
" + ",
Cell[BoxData[
\(TraditionalForm\`\(r\_3\) r\_1\)]],
") > 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, \n\n",
Cell[BoxData[
\(TraditionalForm\`\(\ x\^3\)\)]],
"+ a",
Cell[BoxData[
\(TraditionalForm\`x\^2\)]],
"+ bx + c = 0 with a,b,c < 0,\n\nand that we have two complex roots and one \
real. Let ",
Cell[BoxData[
\(TraditionalForm\`r\_1\)]],
"be the real root. Then we can rewrite this equation as \n\n (x -",
Cell[BoxData[
\(TraditionalForm\`\(\ r\_1\)\)]],
")(",
Cell[BoxData[
\(TraditionalForm\`x\^2\)]],
"+ ex + f ) = 0.\n \n For there to be two complex roots we must have ",
Cell[BoxData[
\(TraditionalForm\`e\^2\)]],
"- f4 < 0, which implies in turn that f > 0.\n \n Since c = -",
Cell[BoxData[
\(TraditionalForm\`r\_1\)]],
"f < 0 and f > 0 it follows that ",
Cell[BoxData[
\(TraditionalForm\`r\_1\)]],
"> 0.\n \n 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.\n \n Let A = ",
Cell[BoxData[
FormBox[
RowBox[{" ",
RowBox[{\(x\^3\), "-", " ",
RowBox[{"2",
FormBox[\(x\^2\),
"TraditionalForm"]}], "+", " ",
RowBox[{
RowBox[{"(",
RowBox[{
FormBox[\(u\^2\),
"TraditionalForm"], "-", " ", "au"}], ")"}], "x"}], " ",
"-", " ",
RowBox[{"a",
FormBox[\(\[Beta]\^2\),
"TraditionalForm"]}]}]}], TraditionalForm]]],
". Then l'(x) =",
Cell[BoxData[
FormBox[
SuperscriptBox[
RowBox[{"(",
RowBox[{
FormBox[\(\[Beta]\^2\),
"TraditionalForm"], "+", " ",
FormBox[\(x\^2\),
"TraditionalForm"]}], ")"}], \(\(-1\)\/2\)],
TraditionalForm]]],
Cell[BoxData[
\(TraditionalForm\`\((x - u)\)\^\(-2\)\)]],
"A. It is sufficient to show that dA/dx > 0 at x = r. We see that\n \n \
dA/dx = 3",
Cell[BoxData[
FormBox[
FormBox[\(x\^2\),
"TraditionalForm"], TraditionalForm]]],
"- 4ux + ",
Cell[BoxData[
\(TraditionalForm\`u\^2\)]],
" - au\t\t(4)\n \n Evaluating (4) at x = r we obtain\n \n dA/dx(r) = 3",
Cell[BoxData[
\(TraditionalForm\`r\^2\)]],
"- 4ur + ",
Cell[BoxData[
\(TraditionalForm\`u\^2\)]],
" - au\n\t= (2",
Cell[BoxData[
\(TraditionalForm\`r\^2\)]],
"- 2ur) + (",
Cell[BoxData[
\(TraditionalForm\`r\^2\)]],
" - 2ur + (",
Cell[BoxData[
\(TraditionalForm\`u\^2\)]],
"- au))\n\t= (2",
Cell[BoxData[
\(TraditionalForm\`r\^2\)]],
"- 2ur) + a",
Cell[BoxData[
\(TraditionalForm\`\[Beta]\^2\)]],
"/r, since ",
Cell[BoxData[
\(TraditionalForm\`r\^3\)]],
"- 2u",
Cell[BoxData[
\(TraditionalForm\`r\^2\)]],
"+ (",
Cell[BoxData[
\(TraditionalForm\`u\^2\)]],
"- au)r - a",
Cell[BoxData[
\(TraditionalForm\`\[Beta]\^2\)]],
"= 0.\n\t= 2r(r - u) +a",
Cell[BoxData[
\(TraditionalForm\`\[Beta]\^2\)]],
"/r.\t\t(5)\n\t\nSince 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.\t\n\n \n\n \n\n\n"
}], "Text",
TextAlignment->Left],
Cell[BoxData[
\(Get::"noopen" \( : \ \) "Cannot open \!\(\"HTML.nb\"\)."\)], "Message"],
Cell["", "Text"]
},
FrontEndVersion->"Macintosh 3.0",
ScreenRectangle->{{0, 1152}, {0, 850}},
WindowToolbars->{},
WindowSize->{581, 789},
WindowMargins->{{43, Automatic}, {3, Automatic}},
Magnification->1.25,
StyleDefinitions -> "HTML.nb",
MacintoshSystemPageSetup->"\<\
00l0001804P000000b02@91H`85N0?N0@00005X0FP000003j0:l001
0@00I00100000@0200000BL?00400000000000000000030001000000000@0?ne
oj/@7@]50200000000000000000001T1\>"
]
(***********************************************************************
Cached data follows. If you edit this Notebook file directly, not using
Mathematica, you must remove the line containing CacheID at the top of
the file. The cache data will then be recreated when you save this file
from within Mathematica.
***********************************************************************)
(*CellTagsOutline
CellTagsIndex->{}
*)
(*CellTagsIndex
CellTagsIndex->{}
*)
(*NotebookFileOutline
Notebook[{
Cell[1709, 49, 11885, 373, 2071, "Text"],
Cell[13597, 424, 91, 1, 28, "Message"],
Cell[13691, 427, 16, 0, 36, "Text"]
}
]
*)
(***********************************************************************
End of Mathematica Notebook file.
***********************************************************************)