Browse Prior Art Database

THE MEAN DISTANCE IN 2-SPACE Disclosure Number: IPCOM000147925D
Original Publication Date: 1976-Jun-30
Included in the Prior Art Database: 2007-Mar-28

Publishing Venue

Software Patent Institute

Related People

Yuval, G.: AUTHOR [+2]


G. Yuval

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 23% of the total text.

Page 1 of 14


G. Yuval

June 1976

Department of Computer Science

Carnegie-Mellon University

Pittsburgh, Pa., 15213

An o(N~) lower bound is proven for the mean distance between N points in 2- space, using methods from complex function theory; but if any 'finite error is allowed, an O(NlogN) algorithm is shown for computing the mean distance to within that finite error.

This research was supported in part by the National Science Foundation under grant MCS75-222-55 and the Office of Naval Research under contract N00014-76-C-0370, NR 044-422.

[This page contains 1 picture or other non-text object]

Page 2 of 14

[This page contains 1 picture or other non-text object]

Page 3 of 14


In this paper, we prove a lower bound for a problem -- finding the mean Euclidean distance between N points in 2-space -- by methods drawn from complex function theory. The crucial fact we shall use is that two complex functions (under the appropriate caveats) can either be identical everywhere, or else they can be identical (almost) nowhere; there is no in-between possibility.

Because of this, a well-behaved function can be continued uniquely everywhere, given its values in any interval, no matter how small. If it has singularities, we can continue it along any path that circumvents them; this may cause the function to become multivalued (depending on whether we circumvent a singularity from the left


or from the right), in which case we say it has a many-sheeted Riemann surface .

 The square-root function, used in the definition of the mean distance, has a 2- sheeted Riemann surface; that is, a square root can have 2 values. This causes the mean distance to have very many possible values. Using analytic continuation, we show that any algorithm that computes it on the reals has to compute it everywhere, and must therefore give equally many different results on the different sheets. A simple argument of accounting for all this ambiguity shows that this implies a large complexity.

 The methods used here should be applicable to other algorithms that use functions with nontrivial Riemann surfaces (e.g. the harmonic mean distance in 2-space, or the gravitational potential energy of N stars).

wish to thank D.Jefferson for some most valuable discussions.

'~eaders unfamiliar with Riemann surfaces might find [I] useful.

[This page contains 1 picture or other non-text object]

Page 4 of 14

Let N points (Xi,Yi) be given in 2-space. The mean distance D between them is defined as


where M is N(N-1)/2.

We can consider D as a function of 2N com~lex variables. For each of the M square roots, there are (complex) points where that square root alone is singular, and all the others are analyticT. 'continuing D on a contour around such a point will reverse the sign of the relevant square root, leaving the others unchanged. Therefor...