Kolme pistettä voidaan asettaa tasoon siten että jokainen on yhtä kaukana toisista (tasasivuisen kolmion kärjet).
Neljää näin ei voida asettaa. Mikä olisi kuitenkin muodostelma, jossa tämä tilanne olisi mahdollisimman lähellä, eli kaikki kahden pisteen väliset etäisyydet olisivat mahdollisimman lähellä toisiaan. (Siis täytyy minimoida näiden etäisyyksien muodostaman (1d-joukon) halkaisija).
[Voidaan skaalata tätä muodostelmaa (eli neljän pisteen tason joukkoa) siten että tuo haluttu kahden pisteen välinen etäisyys olisi 1, jolloin jokainen kahden pisteen välinen etäisyys on mahdollisimman lähellä ykköstä. ]
Yleistettynä:
Miten voidaan k pistettä asettaa n-uloitteiseen euklidiseen avaruuteen siten, että jokaisen kahden pisteen väliset etäisyydet (näitä lukuja on 2 yli k kappaletta) olisi, jos eivät yhtä suuria, niin mahdollisimman lähellä toisiaan?
n 1 kappalettahan voidaan n-uloitteiseen aina tällä tavoin isometrisesti asettaa, mutta useampaa ei. (tasasivuinen kolmio, tetraedri jne.)
Onkohan tätä ongelmaa aikaisemmin tutkittu?
Neljää näin ei voida asettaa. Mikä olisi kuitenkin muodostelma, jossa tämä tilanne olisi mahdollisimman lähellä, eli kaikki kahden pisteen väliset etäisyydet olisivat mahdollisimman lähellä toisiaan. (Siis täytyy minimoida näiden etäisyyksien muodostaman (1d-joukon) halkaisija).
[Voidaan skaalata tätä muodostelmaa (eli neljän pisteen tason joukkoa) siten että tuo haluttu kahden pisteen välinen etäisyys olisi 1, jolloin jokainen kahden pisteen välinen etäisyys on mahdollisimman lähellä ykköstä. ]
Yleistettynä:
Miten voidaan k pistettä asettaa n-uloitteiseen euklidiseen avaruuteen siten, että jokaisen kahden pisteen väliset etäisyydet (näitä lukuja on 2 yli k kappaletta) olisi, jos eivät yhtä suuria, niin mahdollisimman lähellä toisiaan?
n 1 kappalettahan voidaan n-uloitteiseen aina tällä tavoin isometrisesti asettaa, mutta useampaa ei. (tasasivuinen kolmio, tetraedri jne.)
Onkohan tätä ongelmaa aikaisemmin tutkittu?
Vastaukset 5
Vanhimmat
Siis yksinkertaisemmin (?) sanottuna:
Miten voidaan metrinen avaruus X = ( {1, 2, ..., k}, diskreetti metriikka) upottaa R^n:ään (normaali metriikka) siten, että kuvaus olisi mahdollisimman lähellä isometriaa?
Siis tarkemmin: jos F = { f : X -> R^n | f on upotus (jatkuva injektio) }, niin kysytään lukua
d = inf ( | 1 - f(s) | ), missä infimum on yli funktioiden f € F.
Ja jos tämä infimum saavutetaan jollain f € F, niin millä kaikilla?
Sori unohdin ne pisteparit tuosta inf-määritemästä! Pitäisi olla:
d = inf max ( | 1 - |f(s)-f(t)| | ), missä maksimi on yli kaikkien pisteparien {s, t} joukosta {1, ..., k} ja infimum on yli funktioiden f € F.
Tehtävä vaikuttaa huonosti määriteltynä koska ei ole annettu kriteeriä sille, miten lasketaan poikkeama ideaalitilanteesta jossa kaikki pisteet ovat yhtä lähellä toisiaan. Esim. neliöllä pisteiden etäisyydet ovat 1, 1, 1, 1, sqrt2, sqrt2. Miten lasketaan poikkeama?
Tässä neliön tapauksessa poikkeama olisi
| 1- sqrt2 |
eli poikkeama on kaikista mahdollisista kahden pisteen välisistä etäisyyksistä suurin vähennettynä näistä pienin.
Sanoin sen ehkä vähän monimutkaisesti tuossa lauseessa:
"(Siis täytyy minimoida näiden etäisyyksien muodostaman (1d-joukon) halkaisija)".
Tuo (korjattu) inf max - juttu sanoo sen mielestäni tarkasti. Tässä siis valittu, että ideaalitilanteessa kaikki etäisyydet olisivat 1.
Yhtäpitävää olisi luultavasti sanoa, että täytyy minimoida näiden etäisyyksien varianssi (neliösumma etäisyyksistä keskiarvoon).
Otanpa sen verran takaisin, että en olekaan ihan varma onko sama asia "missä metriikassa" tätä minimoi.
Neliösummilla on helpompi laskea, joten lähdin tuota neljän pisteen sijoittamista tasoon miettimään näin:
Ensimmäinen piste voidaan sijoittaa origoon ja toinen kiertää pisteeksi (1, 0), sillä siirto ja kierto ovat isometrioita. Nyt on siis vielä kaksi pistettä vapaasti sijoitettavissa, eli neljä vapaata koordinaattia. Olkoot ne (x, y, z, w) ja sijoitettavat pisteet A = (x, y) ja B = (z, w). Halutaan, että neljän pisteen kuviossa kaikki pisteiden väliset etäisyydet ovat mahdollisimman lähellä lukua d = viides muuttuja (d voidaan siis valita skaalauksen avulla).
Olisi voitu myös valita d=1 ja antaa x-akselilla olevan pisteen (joka nyt valittu pisteeksi (1,0)) liikkua x-akselilla.
Nyt sain minivoitaksi lausekkeeksi
(d-x^2-y^2)^2
(d-z^2-w^2)^2
(d-(x-z)^2-(y-w)^2)^2
(d-(1-x)^2-y^2)^2
(d-(1-z)^2-w^2)^2
(d-1)^2