icsrc@nero.cs.montana.edu (Rob Cimikowski) (10/01/90)
About a week ago I posed the following computational geometry
question to comp.theory:
1) Given a set of points in 3-dimensional space, what is the maximum
number which can be mutually equidistant? (is it 4?) Can the answer
be generalized for n dimensions?
2) Are there any good algorithms for finding a maximum set of
mutually equidistant points in 3 dimensions, that is, better than the
brute-force O(n**4) method of looking at all possible
subsets of 4 points?
I appreciate the many responses I received. Here is a
summary:
From samir@umiacs.UMD.EDU Tue Sep 25 10:00:33 1990
Received: by birdy.umiacs.UMD.EDU (5.61/UMIACS-0.9/04-05-88)
id AA03690; Tue, 25 Sep 90 11:59:41 -0400
Date: Tue, 25 Sep 90 11:59:41 -0400
From: samir@umiacs.UMD.EDU (Samir Khuller)
Message-Id: <9009251559.AA03690@birdy.umiacs.UMD.EDU>
To: icsrc@caesar.cs.montana.edu
Subject: your problem
Status: R
Hi,
I think that there can be only 4 in 3-d, and in general (n+1) in
n dimensions. (I am still trying to work out a formal proof.) Check
with some mathematicians, since they would know an immediate proof
i am sure. It probably has something to do with the concept of a
simplex in d dimensions. Eg, in 2-d its easy to see why there can be
atmost 3 such points (take a pair and then draw 2 circular arcs with
the radius = interpoint distance) these cut in 2 places where we
can put the third point.
An n^3 alg is easy, after you fix 3 points there can be only 2 possible
locations for the 4th (we can compute this location, and then check to see
if there is a point there or not). Perhaps this checking adds a log factor
due to some point location.
more later, samir
From fry@zariski.harvard.edu Mon Sep 24 23:03:40 1990
Date: Tue, 25 Sep 90 01:06:00 EDT
From: fry@zariski.harvard.edu (David Fry)
Message-Id: <9009250506.AA19225@zariski.harvard.edu>
To: icsrc@nero.cs.montana.edu
Subject: Re: comp. geometry
Newsgroups: comp.theory
In-Reply-To: <2473@dali>
Organization: Harvard Math Department
Cc:
Status: R
I don't have any information about question #2, but I think I
can provide a sketch of a proof for #1. The maximal number of
equidistant points is indeed N+1, in dimension N.
Let p(1), p(2), ... p(N) be N equidistant points, with their
coordinates given by p(k) = ( x^1(k), x^2(k), ... x^N(k) ).
If the points are all M units apart, then we're looking for
point p(N+1) as a solution to
for all 1 <= i <= N,
d( p(i), p(N+1) ) = M,
or
sum(k = 1 to N) ( x^k(i) - x^k(N+1) )^2 = M^2.
This is N quadratic equations in N unknowns (the coordinates
( x^1(N+1), x^2(N+1), ... , x^N(N+1) ) are the unknowns). It
can be shown that this will give two unique solutions p(N+1)
which are reflections of each other in the hyperplane spanned
by the points p(1), p(2), ... , p(N), and the distance between
the solutions will NOT be M.
Therefore, given a collection of supposedly equidistant N+2
points, take the first N and construct another point Q using
this method. Either the N+1st or N+2st point must be equal to
Q, but then the point that is not Q could not be equidistant.
I guess that sounds pretty bad, but I'm sure you get the
idea.
David Fry fry@math.harvard.EDU
Department of Mathematics fry@huma1.bitnet
Harvard University ...!harvard!huma1!fry
Cambridge, MA 02138
From edels@cs.uiuc.edu Tue Sep 25 10:07:26 1990
Received: by edels.cs.uiuc.edu id AA03102
(5.64+/IDA-1.3.4 for icsrc@caesar.cs.montana.edu); Tue, 25 Sep 90 11:05:54 -0500
Date: Tue, 25 Sep 90 11:05:54 -0500
From: Herbert Edelsbrunner <edels@cs.uiuc.edu>
Message-Id: <9009251605.AA03102@edels.cs.uiuc.edu>
To: icsrc@caesar.cs.montana.edu
Subject: mutually equidistant
Status: R
1) Yes, if 4 points in 3 dimensions are mutually equidistant
then they form a regular tetrahedron, and no other point
can have the same distance from the 4 points, so 4 is the
maximum. In d dimensions the maximum is d+1.
2) An ad-hoc solution to finding all 4-tuples of mutually
equidistant points is to look at all pairs of points.
Let a and b be such a pair and let 1 be their distance.
Now find all points that lie on the circle of points that
have distance 1 from both a and b. If we sort these
points we can find all points c and d with a,b,c,d
a regular tetrahedron.
The algorithm in 2 is very ad-hoc ... since I didn't really
think about the problem ... but it seems it runs in time
n^3 logn, so faster than the trivial algorithm. It is my
hunch that a lot of time can be saved if one takes advantage
of the fact that the algorithm really batches many problems
of the same kind.
Herbert Edelsbrunner
From <@VM1.NoDak.EDU:stolfi@src.dec.com> Tue Sep 25 13:07:56 1990
Received: from decpa.pa.dec.com by VM1.NoDak.EDU (IBM VM SMTP R1.2.1MX) with TCP; Tue, 25 Sep 90 14:07:12 CDT
Received: by decpa.pa.dec.com; id AA10344; Tue, 25 Sep 90 12:07:19 -0700
Received: by jumbo.pa.dec.com; id AA13617; Tue, 25 Sep 90 12:07:13 -0700
From: stolfi@src.dec.com (Jorge Stolfi)
Message-Id: <9009251907.AA13617@jumbo.pa.dec.com>
Date: 25 Sep 1990 1207-PDT (Tuesday)
To: Rob Cimikowski <icsrc%nero.cs.montana.edu@VM1.NoDak.EDU>
X-Folder-Carbon: geo
Subject: Re: A couple of questions for computational geometers
In-Reply-To: Message of Tue, 25 Sep 90 11:32:28 -0400
from Rob Cimikowski <icsrc%nero.cs.montana.edu@VM1.NoDak.EDU>
<9009251552.AA01902@Sunburn.Stanford.EDU>
Status: R
1) Given a set of points in 3-dimensional space, what is the maximum
number which can be mutually equidistant? (is it 4?)
Yes. Let a, b, c be three mutually equidistant points. The only points
of space that are equidistannt from these three are the apices of the
two regular tetrahedra with base abc, one on each side of the plane
abc. Since the distance between these two apices is greater then the
distances from either of them to the other tree points, only one of
the apices can be added to the set.
Can the answer be generalized for n dimensions?
A similar argument shows that in R^n you can have at most (n+1) mutually
equidistant points. Let a1,..an be n mutually equidistant points,
and let d be their mutual distance. The only points of R^n that are
at distance d from those n points are the apices u, v of the two regular
n-dimensional simplices with those n points as a facet. The altitude
of such a simplex is d * sqrt((n+1)/2n). The distance between u and
v is twice this altitude, namely d*sqrt(2(n+1)/n). Since sqrt(2(n+1)/n)
is never equal to 1, we conclude that only one of u and v can be added
to the set.
2) Are there any good algorithms for finding a maximum set of
mutually equidistant points in 3 dimensions, that is, better
than the brute-force O(n**4) method of looking at all possible
subsets of 4 points?
Gr\"unbaum and others have shown that for any fixed distance d and
any set of n points in three-space, there are at most 2n-2 pairs of
points that realize the distance d. Therefore, you can list all pairs
of vertices, sort them into bins according to their distance, and then
search inside each bin for two pairs (u,v) and (x,y) such that
dist(u,x) = dist(u,y) = dist(v,x) = dist(v,y) = dist(u,v) = dist(x,y)
Given that there are at most 2n-2 pairs in each bin, and n(n-1)/2 pairs
in total, the worst case for this algorithm is when there are
$\Omega(n)$ bins with $\Omega(n)$ pairs each. In that case the
algorithm will take $O(n^3)$ time---not exceptional, but still better
than $n^4$. (If the points come from a regular grid, the atcual time
will be rather close to this bound.) The algorithm will run in $O(n^2
log n)$ expected time for random points (for a suitable definition
of "random").
Unfortunately, this algorithm doesn't work in R^4 and higher spaces,
because then a bin may contain \Omega(n^2) pairs.
If you want sets of *approximately* equidistant points, then the problem
gets a bit harder. Some variant of the bin idea above may still work.
I believe that Ken Clarkson at Bell Labs has worked on this problem.
Here are some related entries from my pile of references.
Sorry for the TeX grot...
\ref\r[GS-246]
\auth{P. <Erd\H os>}
\tit{On sets of distances of $n$ points in Euclidean space.}
\pub{(publication unknown)}
\rem{Let $g_k(n,r)$ be the maximum number of times a given distance $r$
can occur within a set of $n$ points in $\reals^k$ with diameter 1. It
is well-known that $g_2(n,1)=n$ (i.e., the diameter of a set of $n$
points on the plane can be realized by at most $n$ pairs of its points).
Erd\H os \r[GS-247] showed that $$n^{1+c/\log\log n} \lss \max_r
g_2(n,r) \lss n^{3/2},$$ and conjectured that $g_2(n,r) \lss n^{1+\epsilon}$
for every $\epsilon \gtr 0$ and for sufficiently large $n$. Gr\"unbaum and
others \r[GS-308], \r[GS-329], \r[GS-607] have shown that
$g_3(n,1)=2n-2$. Lenz (unpublished) showed that $g_4(n,1)\geq \lfloor
{n^2\over 4}\rfloor$, by taking $n/2$ points on each of two circles of
radius $1/\sqrt{2}$ centered at the origin and located in two orthogonal
planes of $\reals^4$. \par
Here it is shown that $$\alpha n^{4/3} \lss \max_r g_3(n,r) \lss \beta
n^{5/3}$$ for certain constants $\alpha, \beta$. It is conjectured that
$g_3(n,r) \lss n^{4/3+\epsilon}$ for all positive $\epsilon$ and
sufficiently large $n$.\par
The lower bound proof is constructive, giving $\alpha=1/7$. An implicit
formula for $\beta$ is also given. Erd\H os says he has a more involved
proof of a $\Omega(n^{4/3} \log \log n)$ lower bound for $\max_r
g_3(n,r)$, using number-theoretic arguments..}
\top{diameter of a set, furthest neighbors problems, pattern matching,
all nearest neighbors problem, distance problems.}
\ref\r[GS-247]
\auth{P. <Erd\H os>}
\tit{On sets of distances of $n$ points.}
\pub{American Mathematical Monthly vol. 53 (1946), 248--250.}
\rem{Let $F(P)$ be the number of different distances determined by a
set $P$ of points on the plane, and let
$f(n)$ be the minimum of $F(P)$ over all sets $P$ with $n$ points.
Clearly, $f(3)=1$ (equilateral triangle), $f(4)=2$, $f(5)=2$.
The paper proves that $(n-3/4)^{1/2}-1/2 \leq f(n) \leq c n /(log n)^{1/2}$.
For $n$ points in $k$-dimensional space, the same techniques give
$c_1 n^{1/k}\lss f(n) \lss c_2 n^{2/k}$.
The author conjectures also that if the points are the vertices of a convex
polygon, then $f(n)\geq [n/2]$, with equality valid when the polygon is
regular.
Let $g(n)$ be the maximum number of pairs at distance 1 that can occur in a
set of $n$ points on the plane. The author proves that $n^{1+c/\log\log
n}\lss g(n)\lss n^{3/2}$. It is known that among all sets with diameter 1,
the distance 1 can occur at most $n$ times. <V\'azsonyi> conjectured that
in a set of diameter 1 in three-space, the distacne 1 cannot occur more than
$2n-2$ times. If one could prove that in $k$ space the diameter cannot
occur more than $kn$ times, it would follow that every set of diameter $d$
in $k$-space can be decomposed into $k+1$ subsets with diameter les than $d$.
The paper proves also that on the plane, the girth (minimum pairwise
distance) of a set of $n$ points can occur at most $3n-6$ times.}
\ref\r[GS-308]
\auth{B. <Gr\"unbaum>}
\tit{A proof of V\'azsonyi's conjecture.}
\pub{Bulletin of the Research Council of Israel Vol. 6A (1956), 77-78.}
\rem{The diameter of a set of $n$ points in $\reals^3$ is realized by at
most $2n-2$ pairs of its elements.}
\ref\r[GS-329]
\auth{A. <Heppes>}
\tit{Beweis einer Vermutung von A. V\'azsonyi.}
\pub{Acta Math. Acad. Sci. Hung. Vol. 7 (1957) 463--466.}
\rem{The diameter of a set of $n$ points in $\reals^3$ is realized by at
most $2n-2$ pairs of its elements.}
\ref\r[GS-607]
\auth{S. <Straszewicz>}
\tit{Sur un probl\`eme geometrique de P. Erd\H os.}
\pub{\missing Bull. Acad. Poll. Sci. Cl. III Vol. 5 (1957), 39--40.}
\rem{The diameter of a set of $n$ points in $\reals^3$ is realized by at
most $2n-2$ pairs of its elements.}
Hope it helps,
--jorge
PS. Could you please post a summary of the replies you get?
Thanks...
Here is an idea for an O((n**2)logn) algorithm:
(1) calculate distance between all pairs of points
(2) sort this list to find equidistant pairs.
-steve
From ROBERTO@EMDCCI11.EARN Wed Sep 26 06:13:50 1990
Received: by terra.oscs.montana.edu (1.2/Ultrix2.0-B)
id AA09752; Wed, 26 Sep 90 06:13:50 mdt
Message-Id: <9009261213.AA09752@terra.oscs.montana.edu>
Received: From emdcci11.bitnet By mtsunix1.bitnet ; 26 Sep 90 12:13:44 GMT
Received: from EMDCCI11 (ROBERTO) by EMDCCI11 (Mailer R2.07) with BSMTP id
1684; Wed, 26 Sep 90 12:28:22 HOE
Date: Wed, 26 Sep 90 12:27:25 HOE
From: Roberto Moriyon <ROBERTO@EMDCCI11>
Subject: Your message on Theorynet
To: Bob Cimikowski <icsrc@caesar.cs.montana.edu>
Status: R
This is a partial answer to your questions related to equidistant points
in space.
1) The maximum number of equidistant points in N-dimensional space is
N+1. You prove it by induction on N as follows:
a) It is trivial for N=0.
b) For each N you prove as part of the induction process that
i) (N+1) equidistant points in N-dim space are always
independent from the affine point of view (they are
not contained in a hyperplane).
ii) For those points there is a unique point that is at the
same distance of all of them (the baricenter).
iii) The distance between the points is larger than the
distance between one of them and the baricenter multiplied
by the square root of two.
Then you prove the existence of (N+2) equidistant points in
(N+1)-dimensional space by considering (N+1) equidistant points in
the space x=0 and taking the extra point in the line perpendicular
to that space through the baricenter. By iii), you prove the existence
of the new baricenter. The proof of iii) for the (N+2) points is
simple, since the formulas for both distances as a function of the
previous case is explicit.
The same proof tells you that there are only two possible choices
for the (N+2)nd point, and the fact that the distance between them is
bigger than the distance to the other points proves that the maximum is
actually (N+2) in the (N+1)-dimensional case.
2) I find it difficult to get an algorithm better than brute-force, since
you can think of a set of (2m+1) points on the unit disk in 3-dim space
consisting of the origin plus m couples of points located on different
meridians of the sphere forming equilateral triangles with the origin.
In that case it is hard to think of any algorithm that wouldn't find
those triangles in O(m**3) and check whether each of them is part of
a bigger set of 4 equidistant points.
In any case, I am just an amateur about algorithms, so this can be
completely wrong.
Roberto Moriyon
Institute for Knowledge Engineering and Univ. Autonoma de Madrid
e-mail: roberto@emdcci11.bitnet
From orourke%sophia@CS.UMASS.EDU Wed Sep 26 06:56:46 1990
Received: from SOPHIA.DECnet MAIL11D_V3 by dime.cs.umass.edu (5.61/Ultrix2.0-B)
id AA09148; Wed, 26 Sep 90 08:56:05 -0400
Date: Wed, 26 Sep 90 08:56:05 -0400
Message-Id: <9009261256.AA09148@dime.cs.umass.edu>
From: orourke%sophia@CS.UMASS.EDU (Joe O'Rourke)
To: icsrc@caesar.cs.montana.edu
Subject: repeated distances in 3-space
Status: R
Bob:
It is known that there can be about $\Omega(n^{4/3})$
repeated distances, and that there can be no more than about
$O(n^{3/2})$. I say "about" because I am ignoring $\log$'s
and other less important factors in these complexities. This
is a fifty year old problem posed by Erdos. See Discrete and
Computational Geometry, Vol. 5, No. 2, 1990, Clarkson et al,
``Combinatorial complexity bounds for arrangements of curves and
spheres'' for the latest advance of which I am aware. This
paper, and the others in that issue, imply algorithms for finding
the subsets you seek, but it may not be easy to extract this
information from the papers. You might correspond with Edelsbrunner
on this topic. His email address is edels@edels.cs.uiuc.edu.
:-j
----------------------------------------------------------------------
Internet: orourke%sophia@cs.umass.edu
Bitnet: jorourke@smith.bitnet
Joseph O'Rourke | (home)
Dept. of Computer Science | 12 Birch Lane
Stoddard 13 | Northampton, MA 01060
Smith College | (413) 586-9388
Northampton, MA 01063
(413) 585-3673
From dali.cs.montana.edu!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!usc!apple!uokmax!munnari.oz.au!metro!usage.csd.unsw.oz.au!usage.csd!lambert Wed Sep 26 10:47:04 MDT 1990
Article: 1297 of comp.theory
Path: dali.cs.montana.edu!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!usc!apple!uokmax!munnari.oz.au!metro!usage.csd.unsw.oz.au!usage.csd!lambert
From: lambert@spectrum.cs.unsw.oz.au (Tim Lambert)
Newsgroups: comp.theory
Subject: Re: comp. geometry
Message-ID: <LAMBERT.90Sep25234454@nankeen.spectrum.cs.unsw.oz.au>
Date: 25 Sep 90 13:44:54 GMT
References: <2473@dali>
Sender: news@usage.csd.unsw.oz.au
Organization: EE & CS, Uni of NSW, Australia
Lines: 17
In-reply-to: icsrc@nero.cs.montana.edu's message of 24 Sep 90 21:03:31 GMT
>>>>> On 24 Sep 90 21:03:31 GMT, icsrc@nero.cs.montana.edu (Rob Cimikowski) said:
> 2) Are there any good algorithms for finding a maximum set of
> mutually equidistant points in 3 dimensions, that is, better than the
> brute-force O(n**4) method of looking at all possible
> subsets of 4 points?
For each point
sort the other points by the distance to the selected point
Check any triples that end up equidistant from the selected point
This is O(n^2log n).
I suppose you might get it down to O(n^2) with the right data
structure for the points, so that you could get the sorted distances
in linear time.
Tim
From kearns@cs.columbia.edu Wed Sep 26 12:15:52 1990
Received: by cs.columbia.edu (5.59++/0.4)
id AA19659; Wed, 26 Sep 90 14:15:25 EDT
Date: Wed, 26 Sep 90 14:15:25 EDT
From: Steve Kearns <kearns@cs.columbia.edu>
Message-Id: <9009261815.AA19659@cs.columbia.edu>
To: icsrc@nero.cs.montana.edu
Subject: O((n**2)logn) alg
Status: R
(1) calculate distance between all pairs of points
which provides a list of n**2 triples (distance, p1, p2)
where distance is the distance between p1 and p2.
(2) sort this list on the first field, distance, with a secondary key
being the second field, p1. Then, just by scanning this
list you can find a point which is equidistant from 2 other points
by searching for some contiguous triples which have the same distance
and p1 fields. If the two triples are (100, p1, p50) and (100, p1, p4)
then the final step is to do a binary search on the sorted list looking
for (100, p4, p50). If it is present, then p1-p4-p50 are equidistant,
else they are not.
-steve