Minimum numbe o di e en dis ances de ined by a ini e numbe o
poin s
Albuje , A. aand Segu a Gomis, S. a
aDepa amen o de An´alisis Ma em´a ico, Uni e sidad de Alican e, Campus de San Vicen e del Raspeig, E-03080-Alican e,
Spain
Abs ac
We s udy he minimum numbe o di e en dis ances de ined by a ini e numbe o poin s in he ollowing cases:
a) we conside me ics di e en om he euclidean dis ance in he plane, b) we conside he euclidean dis ance
bu es ic ed o subse s o he plane o special in e es , c) we conside o he opological su aces: he cylinde
and he la o us. All hese esul s ex end hose ob ained by E d¨os and o he ma hema icians o he euclidean
dis ance in he plane.
Key wo ds: dis ances, me ics, in ege la ice, la o us, cylinde
1. In oduc ion
In 1946 [4] E d¨os posed he ollowing p oblem:
le (n) deno e he minimum numbe o dis inc
dis ances ha can occu among he n(n−1)
2dis-
ances be ween ndis inc poin s in he plane; wha
can we know abou (n)?
Fo small alues o ni is easy o compu e (n)
and many imes he numbe (n) is a ained o
di e en con igu a ions. Le us see he i s exam-
ples.
...............
.
.
.
.
.
.
.
.
.
.
.
.
.
...................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
..............
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...............
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
(3) = 1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
........
(4) = 2
.
.
.
.
.
.
.
..
.
.
.
.
.
.
..............
..............
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
(5) = 2 (6) = 3
E d¨os ob ained asymp o ic es ima es o (n).
The i s asymp o ic es ima e was
cn1/2< (n)< c n
(ln n)1/2
Email add esses: [email protected] (Albuje , A.),
Sal ado .Segu [email protected] (Segu a Gomis, S.).
E d¨os conjec u ed ha (n)> cn1−ε o each
ε > 0 and o e ed 500$ o a p oo o a disp oo .
E d¨os conjec u e is s ill open. The las imp o e-
men was made by Szeme ´edi (1992) who p o ed
ha (n)> cn4/5([2]).
(n) can be in es iga ed in dimension Rd
wi h d > 2. Fo d= 3 he bes bounds a e
cn4/3log log n < (n) ([5]) and (n)< n3/2+o(1)
([3]).
Recen ly B aß([1]) de e mined (n) exac ly in
dimension d= 4.
The e a e also bounds o gene al dimensions.
The aim o his communica ion is o ex end
E d¨os p oblem o o he ambien spaces.
a) Fi s we conside me ics di e en om he
euclidean dis ance in he plane.
b) Then we conside also he euclidean dis ance
bu es ic ed o subse s o he plane o spe-
cial in e es (poin s o he in ege la ice and
poin s o a ional coo dina es).
c) Finally we conside E d¨os p oblem in o he
opological spaces.
20 h EWCG Se ille, Spain (2004)
20 h Eu opean Wo kshop on Compu a ional Geome y
2. E d¨os p oblem conside ing a bi a y
dis ances in he plane
In he plane we can de ine many dis ances. Le
us ecall ha a dis ance in he plane is a map
d:R2×R2→R
such ha
i) d(x, y)≥0, d(x, y) = 0 i x=y
ii) d(x, y) = d(y, x)
iii) d(x, z)≤d(x, y) + d(y, z)
An in e es ing way o de ine a me ic in he plane
is as ollows.
Le us de ine he gauge unc ion g(K, x) o a
closed, con ex se K ela i e o an o igin 0 as
g(K, x) = in {λ:x∈λK, λ > 0}
I is easy o p o e ha i Kis a p ope con-
ex body and 0 ∈in K, he unc ion m(x, y) =
g(K, x −y) almos de ines a dis ance in he plane.
The condi ion ha is iola ed is he symme y con-
di ion m(x, y) = m(y, x) ha holds only i Kis
cen ally symme ic.
So a closed, cen ally symme ic, con ex se K
wi h 0 ∈in K de ines a me ic ([7]).
All hese me ics gene a e he euclidean opol-
ogy.
In he pa icula case ha he se K ha
induce his me ic is a squa e o he ype
h(p, 0),(0, p),(−p, 0),(0,−p)i, hen we ob ain he
amous axi-cab me ic which is also known as
he Manha an me ic. This me ic is pa icula ly
ele an o ou analysis.
The axi-cab me ic can also be de ined as
dT((x1, y1),(x2, y2)) = |x2−x1|+|y2−y1|
We a e going i s o es ima e he minimum num-
be o dis inc dis ances wi h he axi-cab me ic.
We begin showing in able 1 ha he axi-cab
me ic p o ides di e en alues o (n) han hose
alues a ained wi h he euclidean me ic.
(n) Euclidean me ic Taxi-cab me ic
3 1 1
4 2 1
5 2 2
6 3 2
7 3 2
Table 1
Some alues o (n) wi h he axi-cab me ic
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
(3) = (4) = 1 (5) = ... = (9) = 3
Now we a e going o es ima e p ecisely (n).
Lemma 1 Conside ing he axi-cab me ic
(n)≤ ⌈√n⌉−1
PROOF. Le Lbe he la ice gene a ed by he
ec o s (1,1) and (1,-1). Le pbe an in ege numbe
and le Kpbe he poin se de e mined by Kp=
L∩h(0,0),(p−1,−(p−1)),(2(p−1),0),(p−1, p−
1)i.
Conside K⌈√n⌉. This se con ains a leas n
poin s since ⌈√n⌉ · ⌈√n⌉ ≥ √n·√n=n, so we
can always choose npoin s in K⌈√n⌉. As he poin s
in K⌈√n⌉de e mine ⌈√n⌉ − 1 di e en dis ances
among hem, (n)≤ ⌈√n⌉−1

This es ima e is no only an uppe bound bu a
p ecise de e mina ion o he minimum numbe o
dis inc dis ances:
Lemma 2 Conside ing he axi-cab me ic
(n)≥ ⌈√n⌉−1
PROOF. We a e going o gi e a ske ch o he
p oo :
We conside he “me ic ci cum e ences”, which
in ou case a e squa e-shaped, as he locus o he
poin s ha a e a dis ance om a poin p∈R2:
S(p, ) = {x∈R2:dT(p, x) = }
Now we a e going o loca e he maximum num-
be o poin s who de ine a mos mdis ances among
Ma ch 25-26, 2004 Se ille (Spain)
hem. As we a e always dealing wi h a ini e num-
be o poin s, he e would be a leas wo poin s
a,bsuch ha he dis ance be ween hem is he
maximum possible. All he o he s poin s should
be loca ed in he in e sec ion o m“me ic ci -
cum e ences” cen e ed a aand m“me ic ci cum-
e ences” cen e ed a b. I we do no wan o in-
c ease he numbe o di e en dis ances, he adius
o hese “me ic ci cum e ences” a e {id(a,b)
m}m
i=1.
The e a e wo possible si ua ions:
i) All he “me ics ci cum e ences” in e sec
p ope ly. In his case as hey ha e he pseudodisc
p ope y ( he e a e a mos wo p ope in e sec-
ions o each pai o pseudodiscs), hen we ob ain
ha he maximum numbe o possible poin s is
gi en by (m+ 1)2and hey a e dis ibu ed in a
ansla ed o he squa e Km+1. F om his con ig-
u a ion we ob ain ou lowe bound.
ii) The e a e some pai s o “me ic ci cum e -
ences” ha do no in e sec p ope ly bu a e an-
gen . In his case hey a e angen along a s aigh
line segmen . Conside ing he ends o his s aigh
line segmen and aking he “me ic ci cum e -
ences” cen e ed a hese ends we conclude ha
he e a e no mo e han (m+1)2possible loca ions.
So we also each he same lowe es ima e.

I is easy o see ha he a gumen in he p oo
o lemma 2 holds o all me ics gene a ed by he
gauge unc ion o a cen ally symme ic, con ex
se ; as he equali y sign is a ained in he case ha
he body which gene a es he me ic is a squa e,
we can conclude he ollowing co olla y:
Co olla y 3 Among all me ics gene a ed by a
closed, cen ally symme ic, con ex se K, he me -
ics ha gi e he smalles alues o (n)a e hose
in which he me ic is gene a ed by he gauge unc-
ion co esponding o a squa e.
Fo ins ance he axi-cab me ic o he maximum
me ic de ined as
d((x1, y1)(x2, y2)) = max{|x2−x1|,|y2−y1|}
Co olla y 3 does no hold o gene al me ics. Fo
example, le us conside he so called pos o ice
me ic
d((x1, y1)(x2, y2)) = d2((x1, y1),(0,0))
+d2((0,0),(x2, y2))
whe e d2s ands o he euclidean dis ance in he
plane. In his case i is easy o see ha we can
a ange in ini e poin s so ha each pai o hem is
a dis ance one; so (n) = 1 o all n.
(0,0)
3. The minimum numbe o dis inc
dis ances p oblem wi h he euclidean
dis ance in he in ege la ice
I we conside E d¨os p oblem es ic ed o he
in ege la ice we ob ained di e en alues o (n)
as he ollowing able shows:
(n) Plane In ege la ice
3 1 2
4 2 2
5 2 3
6 3 4
7 3 4
Table 2
Some alues o (n) in he in ege la ice
In gene al, we ha e he ollowing uppe bound:
Lemma 4 In he in ege la ice
(n)≤(⌈√n⌉−2)(⌈√n⌉+ 1)
2
PROOF. Le Lbe he in ege la ice and le
Pnbe he poin se Pn=L∩ h(0,0),(0,⌈√n⌉ −
1),(⌈√n⌉ − 1,0),(⌈√n⌉ − 1,⌈√n⌉ − 1)i.Pncon-
ains a leas npoin s.We can compu e he numbe
o dis inc dis ances by conside ing only he dis-
ances be ween (0,0) and he he es o he poin s
below he diagonal o he squa e. Then we ha e a
mos 2 + 3 + ... + (⌈√n⌉ − 1) dis inc dis ances,
20 h Eu opean Wo kshop on Compu a ional Geome y
ha is he sum o he e ms o an a i hme ic p o-
g ession, so (n)≥2 + 3 + ... + (⌈√n⌉ − 1) =
⌈√n⌉(⌈√n⌉−1)
2−1 = (⌈√n⌉−2)(⌈√n⌉+1)
2
(0,0)

The alues o (n) i we es ic o he in ege
la ice a e he same ha i we es ic o he poin s
wi h a ional coo dina es because a ini e numbe
o poin s wi h a ional coo dina es a e included in
an in ege la ice gene a ed by he ec o s (q, 0)
,(0, q) whe e qis he leas common denomina o o
he coo dina es o he poin s ha we a e conside -
ing.
This es ima e o (n) can be applied o com-
pu e s, because he compu e sc een can be ep e-
sen ed as a ini e numbe o poin s wi h a ional
coo dina es.
4. E d¨os p oblem o o he opological
spaces
The i s ma hema icians o conside his p ob-
lem in o he opological spaces we e E d¨os, Hick-
e son and Pach ([6]) who s udied he case o he
sphe e.
We a e going o conside wo o he pa icula
opological su aces: he cylinde and he la o us.
As we can see in able 3, o small alues o nwe
ob ain he same alues o (n) in bo h opological
su aces, bu his do no occu o g ea e alues
o n.
(n) Plane Cylinde Fla o us
3 1 1 1
4 2 1 1
5 2 2 2
6 3 2 2
Table 3
Some alues o (n) in di e en opological su aces
Now, we can gi e uppe bounds o bo h opo-
logical su aces.
Lemma 5 In he la o us
(n)≤(⌊⌈√n⌉/2 + 1⌋+ 2)(⌊⌈√n⌉/2 + 1⌋−1)
2
Lemma 6 In he cylinde
(n)≤(⌊⌈√n⌉/2 + 1⌋+ 2)(⌊⌈√n⌉/2 + 1⌋−1)
2
+(⌊⌈√n⌉/2 + 1⌋)(⌈√n⌉−⌊⌈√n⌉/2 + 1⌋)
We omi he p oo s because hey a e simila o
he p oo o lemma 3. We ha e o conside a pa -
icula la ice and in e sec i wi h he opological
su aces, as he igu e shows. Then, by some a i h-
me ic compu a ions, we ob ain he bounds.
Fla To us Cylinde
Re e ences
[1] B aß, P.: On he maximum numbe o uni dis ances
among npoin s in dimension ou , In ui i e geome y
(Budapes , 1995), 277–290, Bolyai Soc. Ma h. S ud., 6,
J´anos Bolyai Ma h. Soc., Budapes , 1997.
[2] Chung, F. R. K., Szeme di, E. and T o e , W. T.:
The numbe o di e en dis ances de e mined by a
se o poin s in he Euclidean plane, Disc e e Comp.
Geome y 7(1992), 1–11.
[3] Cla kson, K., Edelsb unne , H., Guibas, L., Sha i ,
M. and Welzl, E.:Combina o ial complexi y bounds o
a angemen s o cu es and sphe es, Disc e e Comp.
Geome y 5(1990), 90–160.
[4] E d¨os, P.: On se s o dis ances o npoin s, Ame . Ma h.
Mon hly 53 (1946), 248–250.
[5] E d¨os, P.:On se s o dis ances o npoin s in Euclidean
space, Magya Tudom´anyos Akad´emia M´a ema ikai
Ku a ´o In ´eze K¨ozlem´enyei 7(1960), 165–169.
[6] E d¨os, P. , Hicke son, D. and Pach J.: A p oblem o Leo
Mose abou epea ed dis ances on he sphe e, Ame .
Ma h. Mon hly 96 (1989), 569–575.
[7] Guggenheime , H. W.: Applicable geome y, Robe E.
K iege Publishing Co., Inc. , Hun ing on, New Yo k,
1977.