\input amstex
\input epsf
\documentstyle{amsppt}
\magnification 1200
\define\({\left(}
\define\){\right)}
\define\F{\widetilde F} 
\define\G{\widetilde G} 
\topmatter
\title
On the Optimality of an Algorithm of Reingold and Supowit
\endtitle
\author Peter J. Grabner and Helmut Prodinger\endauthor
\affil 
Department of Mathematics\\
Technical University of Graz, Austria\\
and\\
Department of Algebra and Discrete Mathematics \\
Technical University of Vienna, Austria
\endaffil
\address\hbox{\vbox{\hbox to 6 truecm{P. Grabner\hfill\break}
\hbox to 6 truecm{Institut f\"ur Mathematik A\hfill\break}
\hbox to 6 truecm{Technische Universit\"at Graz\hfill\break}
\hbox to 6 truecm{Steyrergasse 30\hfill\break}
\hbox to 6 truecm{8010 Graz, Austria\hfill\break}} 
\vbox
{\hbox to 8.5 truecm{H. Prodinger\hfill\break}
\hbox to 8.5 truecm{Institut f\"ur Algebra und Diskrete Mathematik\hfill\break}
\hbox to 8.5 truecm{Technische Universit\"at Wien\hfill\break}
\hbox to 8.5 truecm{Wiedner Hauptstra\ss{}e 8--10\hfill\break}
\hbox to 8.5 truecm{1040 Wien, Austria\hfill\break}}}
\endaddress 
\email grabner\@weyl.math.tu--graz.ac.at,
proding\@rsmb.tuwien.ac.at
\endemail
\thanks
\flushpar This research was supported by the Austrian-Hungarian cooperation 
10U3.\newline
The first author is supported by the Schr\"odinger scholarship J00936-PHY.
\endthanks
\abstract
 In \cite{5}, Reingold and Supowit
have analyzed a divide--and--conquer heu\-ristic to obtain a matching with
a small cost. 
In this paper we show that -- among a large class of similar
strategies -- the version of Reingold and Supowit produces the minimal
expected costs.

\endabstract
\endtopmatter
\document


Let $n$ be an even integer, and $P$ a set of $n$ points in the plane.
A matching is a set of $n/2$ edges such that each point of $P$ is
an endpoint of exactly one edge. The sum of the lengths of the edges
is called the cost of the matching. In \cite{5}, Reingold and Supowit
have analyzed a divide--and--conquer heuristic to obtain a matching with
a small cost. In two previous papers \cite{6,7} they have performed a worst-case
analysis of several minimal matching algorithms.

Here, we want to demonstrate, that -- among a large class of similar
strategies -- the version of Reingold and Supowit produces the minimal
expected costs.

For the sake of shortness, we assume a certain knowledge of \cite{5}.

Reingold and Supowit start with a rectangle with sides $\sqrt2$ and
$1$. Then, it is bisected vertically to form two rectangles of sides
$1$ and $1/\sqrt2$, respectively. If both rectangles contain an
even number of points,  the matching is constructed in both
rectangles separately. If both rectangles contain an odd number
of points, the recursive strategy leaves one point in each rectangle
(the ``stranded point''), and the two lonely points are connected.

Now we consider -- more generally -- a rectangle with sides $a$ and $b$.
The first vertical cut produces two rectangles with respective
sides $\frac a2$ and $b$. They are only similar to the original one
in the Reingold/Supowit setting. However, the next cut will be
horizontal, and the produced rectangles are similar to the original one.

Let us now consider the expected costs according to $n$ random points.
They are of course dependent on the size of the rectangle from which
we start. If we multiply both sides by a factor $\lambda$, the 
expected cost will also multiply by the factor $\lambda$. And if we
want to compare the expected costs according to different rectangles,
we should normalize them by dividing by $\sqrt{ab}$.

Instead of one recursion as in the original case, we must consider
$F_n$, the expected cost, based on a rectangle with sides $a$ and $b$,
and $G_n$, the expected cost, based on a rectangle with sides 
$b$ and $\frac a2$.  The fact that one recursion was sufficient to 
compute the expected cost might have been -- apart from some ingenious
intuition -- the motivation of the original setting of Reingold and
Supowit.


Otherwise, the argument to obtain the recursion is pretty
much the same as in \cite{5}.

We have $F_0=G_0=0$, and for $n\ge1$
$$
\aligned
F_n&=2^{-n}\sum_{k=0}^n\binom{n}{k}\Big(G_k+G_{n-k}\Big)+\tfrac12
\phi(a,b)\cdot \chi(n)\\
G_n&=2^{-n}\sum_{k=0}^n\binom{n}{k}\Big(\frac{F_k}2+\frac{F_{n-k}}2\Big)
+\tfrac12
\phi(b,\tfrac a2)\cdot \chi(n)
.
\endaligned\tag1
$$
Here, $\chi(n)$ is 1 for $n$ even and 0 for $n$ odd; the $\tfrac12$
is the probability of an ``odd--odd split'' and $\phi(a,b)$ is the expected
distance between two randomly chosen points one in each of the two
halves (with sides $\tfrac a2$ and $b$) of the rectangle with sides
$a$ and $b$. By symmetry, we can write
$$
\aligned
F_n&=2^{1-n}\sum_{k=0}^n\binom{n}{k}G_k+\tfrac12
\phi(a,b)\cdot \chi(n)\\
G_n&=2^{-n}\sum_{k=0}^n\binom{n}{k}F_k
+\tfrac12
\phi(b,\tfrac a2)\cdot \chi(n).
\endaligned\tag2
$$
Now, $\phi(a,b)=b\cdot g(\frac{a}{2b})$, where $g(a)$ is the expected distance
of two points in each of two adjacent rectangles of sides $a$ and 1 each.
This quantity is given by \footnote{We used Mathematica to compute the four-fold 
integral}

$$\aligned 
g(a)&=\frac1{a^2}\int_0^1\int_0^a\int_0^1\int_0^a\sqrt{(x_1+x_2)^2+(y_1-y_2)^2}\
, dx_1\, dy_1\, dx_2\, dy_2=\cr
{1\over {{a^2}}}\Biggl(&-{1\over {30}} + {a^5} + 
	{{{\sqrt{1 + {a^2}}}}\over {15}} - 
     {{{a^2}\,{\sqrt{1 + {a^2}}}}\over 5} + 
	{{{a^4}\,{\sqrt{1 + {a^2}}}}\over {15}} \cr &- 
     {{{\sqrt{1 + 4\,{a^2}}}}\over {30}} + {{2\,{a^2}\,{\sqrt{1 + 
4\,{a^2}}}}\over 5} - 
     {{8\,{a^4}\,{\sqrt{1 + 4\,{a^2}}}}\over {15}}
- {{{a^4}\,\log (a)}\over {12}} \cr &+ 
     {{5\,{a^4}\,\log (2\,a)}\over 4} + {{{a^4}\,\log (-1 + {\sqrt{1 + 
{a^2}}})}\over 8} - 
     {{{a^4}\,\log (1 + {\sqrt{1 + {a^2}}})}\over {24}} \cr &- 
     {{a\,\log (a + {\sqrt{1 + {a^2}}})}\over 6}
 - 
     {{31\,{a^4}\,\log (-1 + {\sqrt{1 + 4\,{a^2}}})}\over {24}} \cr &+ 
     {{{a^4}\,\log (1 + {\sqrt{1 + 4\,{a^2}}})}\over {24}} + 
     {{a\,\log (2\,a + {\sqrt{1 + 4\,{a^2}}})}\over 6}\Biggr).\endaligned\tag3
$$

We choose an alternative approach to solve the system of recursions \thetag{2}.
Reingold and Supowit have used the Mellin transform, as demonstrated
in Knuth's book \cite{4,p.131ff}, while we use a slightly faster approach,
which is called Rice's method (see \cite{2},\cite{3}).

Let us use two other abbreviations, 
$$
A=\frac12\phi(a,b)=\frac b2\,g(\frac a{2b})\qquad\text{
and}\qquad B=\frac12\phi(b,\frac a2)=\frac a4\,g(\frac{b}{a}).\tag4
$$

It is useful to deal with the exponential generating functions
$$
F(z)=\sum_{n\ge0}F_n\frac{z^n}{n!}\quad\text{and}\quad
G(z)=\sum_{n\ge0}G_n\frac{z^n}{n!}.
$$
Then we get, on summing up the recursions for $n\ge1$,
$$
\aligned
F(z)&=2e^{z/2}G\big(\frac z2\big)+A\frac{e^z+e^{-z}}{2}-A\\
G(z)&=e^{z/2}F\big(\frac z2\big)+B\frac{e^z+e^{-z}}{2}-B
\endaligned\tag5
$$
The next step is to introduce
$$
\F(z)=e^{-z}F(z)=\sum_{n\ge0}\F_n\frac{z^n}{n!}\quad\text{and}\quad
\G(z)=e^{-z}G(z)=\sum_{n\ge0}\G_n\frac{z^n}{n!}.
$$
Then we obtain
$$
\aligned
\F(z)&=2\G\big(\frac z2\big)+A\frac{1+e^{-2z}}{2}-Ae^{-z}\\
\G(z)&=\F\big(\frac z2\big)+B\frac{1+e^{-2z}}{2}-Be^{-z}
\endaligned\tag6
$$
or
$$
\F(z)=2\F\big(\frac z4\big)+B(1+e^{-z})-2Be^{-z/2}+A\frac{1+e^{-2z}}{2}-Ae^{-z}.
$$
 From this we infer that $\F_0=0$ and for $n\ge1$
$$
\F_n=\frac{(-1)^n}{1-2^{1-2n}}\bigg(A(2^{n-1}-1)+B(1-2^{1-n})\bigg).\tag7
$$
Since $F(z)=e^z\F(z)$, we get for $n\ge1$
$$
F_n=\sum_{k=1}^n\binom nk(-1)^k
\frac{1}{1-2^{1-2k}}\bigg(A(2^{k-1}-1)+B(1-2^{1-k})\bigg).\tag8
$$
As already indicated, we use Rice's method \cite{3} for the asymptotic
evaluation of this (alternating) sum. Set
$$
\psi(z)=\frac{1}{1-2^{1-2z}}\bigg(A(2^{z-1}-1)+B(1-2^{1-z})\bigg).\tag9
$$
The basis of the approach is the integral representation
$$
\sum_{k=1}^n\binom nk(-1)^k \psi(k)=-\frac{1}{2\pi i}
\int_{\Cal C}\frac{\Gamma(n+1)\Gamma(-s)}{\Gamma(n+1-s)}\, \psi(s)\,  ds,
\tag10
$$
where $\Cal C$ is a positively oriented closed curve that lies in
the domain of analyticity of $\psi(s)$,  encircles $1,2,\dots,n$ and no
other poles of the integrand.

The asymptotic behavior is obtained by enlarging the contour of integration
and taking the additional negative residues into account; they are
the terms in the asymptotic expansion. In our instance, there are poles
 at $z=\frac12+\frac12\chi_k$,
for $k\in\Bbb Z$,  with $\chi_k=\frac{2k\pi i}{\log2}$, since for these 
values we have $1-2^{1-2z}=0$. All these poles are actually simple.

The computation  of the negative residues at $z=\frac12+\frac12\chi_k$ is 
standard \footnote{We used Maple to
compute the residues} and yields
$$
\frac{\Gamma(n+1)\Gamma(-\frac12-\frac12 \chi_k)}{\Gamma(n+\frac12-\frac12
\chi_k)}
\frac{1}{2\log2}
\bigg(A\Big(\frac{(-1)^k}{\sqrt2}-1\Big)+B\Big(1-\sqrt2(-1)^k\Big)
\bigg).\tag11
$$
Note that by \cite{1}
$$
\frac{\Gamma(n+1)}{\Gamma(n+\frac12-\frac12
\chi_k)}=n^{\frac12+\frac12\chi_k}\(1+\Cal O\Big(\frac{k^2}n\Big)\)
=\sqrt n\cdot e^{2k\pi i\cdot\log_4n}\(1+\Cal O\Big(\frac{k^2}n\Big)\)
$$
and $|\Gamma(\sigma+it)|=\sqrt{2\pi}|t|^{\sigma-\frac12}e^{-\frac\pi2|t|}$.
It is customary to consider the pole at $z=\frac12$ separately.
The contribution is
$$
\sqrt n\cdot \frac{\Gamma(-\frac12)}{2\log2}\Big(A+\sqrt2B\Big)
\frac{1-\sqrt2}{\sqrt2}.\tag12
$$
Note also that $\Gamma(-\frac12)=-2\sqrt\pi$, so that we get
$$
\sqrt n\cdot \frac{\sqrt\pi(\sqrt2-1)}{\sqrt2\log2}\Big(A+\sqrt2B\Big)
.
$$
We collect the residues \thetag{11} and \thetag{12} and get
\proclaim{Theorem 1} The average cost of a random matching obtained
from $n$ points in a rectangle of sides $a$ and $b$ is given by
$$
\sqrt n\cdot \bigg(
\frac{\sqrt\pi(\sqrt2-1)}{\sqrt2\log2}\Big(A+\sqrt2B\Big)
+\delta(\log_4n)+\Cal O\Big(\frac1n\Big)\bigg),
$$
where $\delta(t)$ is a continuous periodic $\Cal C^\infty$-function of period 
$1$ whose Fourier-expansion is given by
$$\delta(t)=\sum_{k\in\Bbb Z\setminus\{0\}}\Gamma\(-\frac12-\frac12 \chi_k\)
\frac{1}{2\log2}
\bigg(A\Big(\frac{(-1)^k}{\sqrt2}-1\Big)+B\Big(1-\sqrt2(-1)^k\Big)
\bigg)e^{2k\pi it};$$
the quantities $A$ and $B$ are given by \thetag4.
\endproclaim

For the ``classical'' case we have $B=A / \sqrt2$,
and the factor in front of $\sqrt n$ is
$$
\frac{\sqrt \pi(\sqrt2-1)\sqrt2A}{\log2},
$$
in accordance with the result in \cite{5},  where the quantity $D$ corresponds
to $2A$.


Now we want to determine which choice of $a$ and $b$ gives the smallest
constant. Apart from factors which do not depend on the design parameters,
we have to consider $A+\sqrt2B$. As already discussed, we must rescale
this quantity by $\sqrt{ab}$. We thus want to minimize
$$
\frac{A+\sqrt2B}{\sqrt{ab}}=\frac12\sqrt{\frac {\mathstrut b}{\mathstrut 
a}}\,g\(\frac{\mathstrut a}{\mathstrut2b}\)+
\frac{\sqrt2}{4}\sqrt{\frac{\mathstrut a}{\mathstrut b}}\,g\(\frac {\mathstrut 
b}{\mathstrut a}\).
$$
As it is to be expected, this quantity depends only on the ratio
$x=\frac ab$, and we have to minimize
$$
H(x):=\sqrt{\frac{\mathstrut 1}{\mathstrut x}}\,g\(\frac {\mathstrut 
x}{\mathstrut 2}\)+\sqrt{\frac{\mathstrut x}{\mathstrut 2}}\,
g\(\frac{\mathstrut 1}{\mathstrut x}\).
$$
It is quite plausible that  $x=\sqrt 2$ minimizes $H(x)$, since
then both terms are the same. Maple can differentiate $H(x)$ and confirms
that $H'(\sqrt 2)=0$. Since the expression for $H'(x)$ is quite involved, we 
will use a different approach
to confirm that the only minimum is obtained for $x=\sqrt2$.

First, we prove that $g(x)$ is convex by proving that $g'(x)$ is monotonically 
increasing. For this purpose
we compute
$$\align 
g'(x)=\frac2{x^3}\int_0^1\int_0^1\int_0^x\int_0^x\Bigl(&\sqrt{(x_1+x)^2+(y_1-y_2
)^2}-\cr
&\sqrt{(x_1+x_2)^2+(y_1-y_2)^2}\Bigr)\,dx_1\,dx_2\,dy_1\,dy_2.\endalign$$
Let now $a<b$. Then we get by substituting $x_1=\frac ab\xi_1$ and $x_2=\frac 
ab\xi_2$
$$\align 
g'(a)=\frac2{b^3}\int_0^1\int_0^1\int_0^b\int_0^b\Biggl(&\sqrt{(\xi_1+b)^2+\frac
{b^2}{a^2}(y_1-y_2)^2}-\cr
&\sqrt{(\xi_1+\xi_2)^2+\frac{b^2}{a^2}(y_1-y_2)^2}\Biggr)\,d\xi_1\,d\xi_2\,dy_1\
,dy_2.\endalign$$
Then we can write $g'(b)-g'(a)$ as a four-fold integral with positive integrand 
and we have proved monotonicity of $g'$.

The next step in proving $H(x)\geq H(\sqrt2)$ is the simple inequality
$$g\(\frac{\mathstrut x}{\mathstrut 2}\)\,g\(\frac{\mathstrut 1}{\mathstrut 
x}\)\geq g\(\frac1{\sqrt2}\)^2,$$
which is an immediate consequence of
$$g(x)\geq g\(\frac1{\sqrt2}\)+g'\(\frac1{\sqrt2}\)\(x-\frac1{\sqrt2}\)$$
and the fact that $\sqrt2\,g(\frac1{\sqrt2})-g'(\frac1{\sqrt2})>0$.
Equality holds, if and only if $x=\sqrt2$. Now we write
$$\align &H(x)-H(\sqrt2)=\sqrt{\frac{\mathstrut 1}{\mathstrut 
x}}\,g\(\frac{\mathstrut x}{\mathstrut 2}\)+
\sqrt{\frac{\mathstrut x}{\mathstrut 2}}\,g\(\frac{\mathstrut 1}{\mathstrut 
x}\)-\frac2{\root 4 \of2}\,g\(\frac1{\sqrt2}\)\geq\cr
&\sqrt{\frac{\mathstrut 1}{\mathstrut  x}}\,g(\frac{\mathstrut x}{\mathstrut 
2})+\sqrt{\frac {\mathstrut x}{\mathstrut 2}}
\,g\(\frac{\mathstrut 1}{\mathstrut 
x}\)-\frac2{\root4\of2}\sqrt{g\(\frac{\mathstrut x}{\mathstrut 2}\)\,
g\(\frac{\mathstrut 1}{\mathstrut x}\)}=\cr
&\({\root4\of {\frac{\mathstrut 1}{\mathstrut x}}}\sqrt{ g\(\frac{\mathstrut 
x}{\mathstrut 2}\)}-
\root4\of{\frac{\mathstrut x}{\mathstrut 2}}\sqrt{g\(\frac{\mathstrut 
1}{\mathstrut x}\)}\)^2\geq0,\endalign$$
which proves the desired result.

We note here that we could not find a simpler proof for this fact, which could 
be read off from the following plot of
$H(x)$, which was produced with Mathematica.


\vskip10truecm


{\bf Acknowledgment.} The second author wants to thank W.~Szpankowski
for interesting discussions.


\Refs
\ref\no 1\by M. Abramovitz and I.A. Stegun\book Handbook of Mathematical 
Functions\publ Dover Publications, Inc.\publaddr New York
\yr 1965\endref

\ref\no 2\by P.~Flajolet and R.~Sedgewick
\paper Digital Search Trees Revisited
\jour SIAM J. Comput.\vol15\pages 748--767\yr1986\endref

\ref\no 3\by P.~Flajolet and R.~Sedgewick\paper
Mellin Transforms and Asymptotics: Finite Differences and Rice's Integrals
\jour Theoret. Comput. Sci.\yr 1995\vol144\pages101--124
\endref

\ref \no 4  \by D.~E.~Knuth \book The Art of Computer Programming,
Vol.~3. \publ Addison-Wesley \yr 1973 \endref

\ref\no5\by E.~M.~Reingold and K.~J.~Supowit
\paper Probabilistic Analysis of Divide--and--Conquer Heuristics for 
Minimum Weighted Euclidean Matching
\jour Networks\vol 13\yr 1983 \pages 49-66
\endref

\ref\no6\by K.~J.~Supowit and E.~M.~Reingold\paper Divide and conquer heuristics 
for
minimum weighted Euclidean matching\jour SIAM J. Comput.\vol 12\pages 
118--143\yr 1983\endref

\ref\no7\by  K.~J.~Supowit, E.~M.~Reingold and D.~A.~Plaisted\paper The 
traveling salesman
problem and minimum matching in the unit square\jour SIAM J. Comput.\vol 
12\pages 144--156
\yr 1983\endref

\endRefs



\enddocument







