Minimum number of different distances defined by a finite number of points

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.