Pontpozicionálás távolságméréssel

Képzeljük el a következő szituációt. A háromdimenziós térben van egy tárgy, $X$ , amelynek pontos helyzetét szeretnénk megtudni. Ehhez van négy állomásunk, $P_{1},P_{2},P_{3}$ és $P_{4}$ , amelyeknek az $X$ -től vett euklideszi távolságait tudjuk mérni. E négy mennyiség alapján meg tudjuk-e állapítani $X$ helyzetét?

Az egyszerűség kedvéért feltesszük, hogy $X,P_{1},P_{2},P_{3}$ és $P_{4}$ helyzete fix, tehát az állomások és a tárgy nem mozognak. Tekintsük előbb a problémát egy egyszerűbb szituációban, a síkon. Ekkor három állomás adott: $P_{1},P_{2}$ és $P_{3}$ , amelyek euklideszi távolságait $X$ -től, azaz $\vert X-P_{1}\vert$ -t, $\vert X-P_{2}\vert$ -t és $\vert X-P_{3}\vert$ -t megmértük, és ez alapján szeretnénk kiszámolni, hogy $X$ hol helyezkedik el. Kérdés, hogy elegendő információ áll-e ehhez a rendelkezésünkre? Vegyük észre, hogy abban a speciális esetben, amikor a három állomás egy egyenesen fekszik, nincs elég információnk, ugyanis ha tükrözzük $X$ -t az állomások által kifeszített egyenesre, akkor a kapott $X'$ pont távolsága nyilván ugyanaz lesz az állomásoktól, mint $X$ -é (lásd az 1. ábrát). Ha viszont feltesszük, hogy a három állomás nem esik egy egyenesre, azaz egy valódi háromszöget feszítenek ki a síkon, akkor már elegendő információnk van ahhoz, hogy $X$ pozícióját meghatározzuk. Ennek bizonyításához két lehetséges gondolatmenet vázolunk, amelyek közül talán az első amire azonnal gondolna az ember, a második pedig egy „fordított gondolatmenet”, amelyről azonban később kiderül, hogy hasznosabb.

1. Vegyük észre, hogy $X$ három körvonal metszetén kell, hogy feküdjön, amelyeknek ez esetben nem lehet egynél több metszéspontja.

2. Tegyük fel, hogy nem igaz az állítás, és van még egy $X'$ pont , amitől mért távolságok egyeznek az $X$ -től mért távolságokkal. Ez azt jelenti, hogy $P_{j}$ távolsága $X$ -től és $X'$ -től megegyezik minden $j=1,2,3$ esetén, azaz $P_{j}$ az $X$ és $X'$ felező merőlegesén kell hogy legyen, ami ellentmond feltevésünknek, hiszen ez egy egyenes (lásd megint az 1. ábrát).

1. ábra. A színes szaggatott vonalak azt jelzik, hogy az adott távolságok megegyeznek. A $P_1$ , $P_2$ , $P_3$ pontokon átmenő egyenes az $X$ és $X'$ pontok felező merőleges egyenese.

Most tekintsük a háromdimenziós esetet. Természetesen, ha az állomások egy síkra esnek, akkor megint csak ha tükrözzük $X$ -et erre a síkra, akkor a kapott $X'$ pont távolsága $P_{j}$ -től ugyanaz mint $X$ -é minden $j$ -re. Ezért itt is feltesszük, hogy $P_{1},P_{2},P_{3}$ és $P_{4}$ nem esik egy síkra. Ez esetben is alkalmazható a fenti első gondolatmenet, de sokkal jobban átlátható a második „ fordított gondolatmenet”. Tehát tegyük fel, hogy nem igaz az állítás, és van még egy $X'$ pont, amitől mért távolságok egyeznek az $X$ -től mért távolságokkal. Ekkor minden $P_{j}$ az $X$ és $X$ felező merőleges síkján található, ami ellentmond feltevésünknek.

A fenti elvet (elhanyagolva az Einstein-féle relativitáselméletet és azt, hogy a méréseink sosem teljesen pontosak) alkalmazza a GPS (Global Positioning System) is, általában 4-5 műhold segítségével tudja műszerünk kiszámolni nagyon pontosan, hogy hol vagyunk.

A matematika különféle ágaiban (elméleti és alkalmazott területeken egyaránt) felmerülnek olyan problémák, amikor szükség van arra, hogy a távolságot nem a fenti euklideszi értelemben mérjük, hanem egy jóval általánosabb, úgynevezett norma segítségével.

Egy $\Vert\cdot \Vert\colon R^{3}\to[0,\infty)$ függvényt normának hívunk, ha teljesíti az alábbi három feltételt:

(pozitív definitség) $\Vert x\Vert\ge 0$ minden $x\in \mathbb{R}^3$ esetén, és $\Vert x\Vert=0$ pontosan akkor ha $x=0$ ,
(pozitív homogenitás) $\Vert\lambda \cdot x\Vert=\vert\lambda \vert\cdot \Vert x\Vert$ tetszőleges $\lambda \in R$ és $x\in \mathbb{R}^3$ esetén,
(háromszög-egyenlőtlenség) $\Vert x+y\Vert\le \Vert x\Vert+\Vert y\Vert$ minden $x,y\in \mathbb{R}^3$ .

Azt mondjuk, hogy $R^{3}$ a $\Vert\ \Vert$ normával felruházva egy háromdimenziós valós normált tér. Ez esetben az $X$ és $Y$ pontok távolságát a $\Vert X-Y\Vert=\Vert\overrightarrow{XY}\Vert$ mennyiség definiálja. Teljesen hasonlóan definiáljuk a kétdimenziós valós normált tereket. Természetesen a szokásos euklideszi norma

$\displaystyle \vert x\vert=\vert( x_{1},x_{2},x_{3})\vert=\sqrt {x_{1}^{2}+x_{2}^{2}+x_{3}^{2}}$

normát definiál $R^{3}$ -on a fenti értelemben.

Most adunk néhány további példát. Tegyük fel, hogy $p\ge \, 1$ valós szám, ekkor az alábbi, $p$ -norma néven ismert mennyiség szintén normát definiál $R^{3}$ -on (hasonlóan $R^{2}$ -n):

$\displaystyle \Vert x\Vert _{p}=\Vert(x_{1},x_{2},x_{3})\Vert _{p}=\sqrt[p]{\vert x_{1}\vert^{p}+\vert x_{2}\vert^{p}+\vert x_{3}\vert^{p}}$ .

A normatulajdonságok közül egyedül a háromszög-egyenlőtlenség nem triviális, amely Minkowski-egyenlőtlenség néven vonult be a történelembe . A figyelmes olvasó észreveheti, hogy a Minkowski-egyenlőtlenség az úgynevezett $p=\infty$ esetben is kimondható.

Egy vektor $\infty$ -normáján a következő mennyiséget értjük:

$\large \|x\|_\infty=\|(x_1,x_2,x_3)\|_\infty=\max(x_1,x_2,x_3).$

Ez ugyancsak normát definiál $R^{3}$ -on. Megjegyezzük, hogy a 2-norma az euklideszi normát adja vissza, illetve, hogy az eddig említett normákon kívül még rengeteg más normát lehet definiálni.

2. ábra. Néhány $p$ -norma egységkörlapja a síkon, balról jobbra haladva a $p=1$ , $\frac{3}{2}$ , 2, 3, 4 és $\infty$ esetek láthatóak.

Egy norma szerinti egységgömbön (a sík esetén egységkörlapon) azon pontok halmazát értjük, amelyek legfeljebb 1 távolságra helyezkednek el az origótól. A 2. és a 3. ábra néhány $p$ -norma egységkörlapját és egységgömbjét illusztrálja a síkon, illetve a térben. Érdekességként megemlítjük, hogy az 1-norma esete Manhattan- vagy taxinorma néven is ismert, hiszen egy Manhattanben (melynek utcái négyzetrácsos mintát adnak) vezető taxisnak (megközelítően) $\Vert X-Y\Vert _{1}$ távolságot kell vezetnie az $X$ ponttól $Y$ -ig.

3. ábra. Néhány $p$ -norma egységgömbje a térben, balról jobbra haladva a $p=1$ , $\frac{3}{2}$ , 2, 3, 4 és $\infty$ esetek láthatóak.

A cikk elején feltett kérdés természetesen felvetődik egy általános norma esetén is, ekkor a kérdés a következőképp hangzik. Tekintsünk egy $\Vert\ \Vert$ normát $R^{3}$ -on és tegyük fel, hogy adott négy pont a térben, $P_{1},P_{2},P_{3}$ és $P_{4}$ . Elegendő információt ad-e a négy $\Vert P_{j}-X\Vert\, (j=1,2,3,4)$ távolság ahhoz, hogy a térben bármely $X$ pontot egyértelműen meg tudjunk határozni? (Hasonló a kérdés $R^{2}$ -n három ponttal). Mivel már az euklideszi esetben is fel kellett tennünk, hogy $P_{1},P_{2},P_{3}$ és $P_{4}$ nem egy síkra esik (hasonlóan $R^{2}$ -n, hogy $P_{1},P_{2}$ és $P_{3}$ nem esik egy egyenesre), mostantól kezdve ezt a cikkben mindig automatikusan fel fogjuk tenni! Mint azt látni fogjuk, általában még ekkor sem elegendő a négy távolság ismerete ahhoz, hogy minden $X$ pontot meg tudjunk határozni a térben. (Megjegyezzük, hogy bár minden esetben bizonyos pontok pozícionálásához ez a négy távolság elegendő, mi ezt minden pontra megköveteljük). Ahhoz hogy ennek okát lássuk, a „fordított gondolatmenetet” fogjuk alkalmazni a normára, de előbb bevezetünk egy fogalmat. Legyen $Y$ és $Z$ két különböző pont a térben, ekkor a

$\displaystyle B(Y,Z):=X\colon\Vert X-Y\Vert=\Vert X-Z\Vert$

halmazt az $Y$ és $Z$ biszektorának hívjuk. Az euklideszi esetben ez egy sík volt (egyenes a sík esetében).

Az euklideszi esetben már elmagyarázott gondolatmenethez hasonlóan kapjuk, hogy az $Y$ és $Z$ pontokat pontosan akkor nem különbözteti meg a $\Vert P_{j}-Y\Vert$ és $\Vert P_{j}-Z\Vert$ ( $j=1,2,3,4$ ) távolságok ismerete, ha a $P_{1},P_{2},P_{3}$ és $P_{4}$ pontok a $B(Y,Z)$ biszektorra esnek. Következésképpen, a $\Vert P_{j}-X\Vert$ távolságok ismerete pontosan akkor elegendő minden $X$ pont pozícionálásához a térben, ha nem létezik két olyan különböző $Y$ és $Z$ pont, amelyek $B(Y,Z)$ biszektorára a $P_{1},P_{2},P_{3}$ és $P_{4}$ pontok esnek.

4. ábra. Egy-egy biszektor a síkon és a térben $p$ -norma esetén, $p=\frac{3}{2}$ .

A fentiek alapján pontosan akkor lenne bármely nem egy síkra eső pontnégyes megfelelő a mi célunknak, ha minden biszektor egy sík lenne (egyenes $R^{2}$ -n). Ismert eredmény, hogy ez pontosan akkor történik, ha a norma euklideszi, azaz ha a norma belső szorzatból származtatható. A híres Jordan—von Neumann-tétel miatt ez ekvivalens azzal, hogy a norma teljesíti a parallelogramma-azonosságot, azaz ha

$\displaystyle \Vert A-B\Vert^{2}+\Vert A+B\Vert^{2}=2\Vert A\Vert^{2}+2\Vert B\Vert^{2}$

teljesül minden $A,B\in \mathbb{R}^3$ esetén.

5. ábra. Biszektor a síkon az 1-norma (Manhattan norma) esetén

Egy biszektor igen különösen is viselkedhet, például bizonyos normák esetén nem mindig ad egy kétdimenziós felületet (a síkon pedig nem mindig egy görbét). Ismert, hogy ez a jelenség nem fordul elő, ha az egységgömb határa nem tartalmaz (nem elfajuló) szakaszt, amely esetben a normát szigorúan konvexnek hívjuk. A fenti $p$ -normák a $1<p<\infty$ esetben szigorúan konvexek, ezért akkor minden biszektor egy kétdimenziós felület (görbe a síkon). A 4. ábra egy-egy példát mutat ilyen biszektorra a síkon és a térben. A $p\in \{1,\infty \}$ esetekben viszont vannak olyan biszektorok, amelyeknek belseje nem üres, s így nem kétdimenziós felület a térben, vagy nem egy görbe a síkon (lásd az 5. ábrát). Megjegyezzük, hogy létezik olyan norma $R^{3}$ -on, amely nem szigorúan konvex, mégis minden biszektor egy kétdimenziós felületet ad. Erre az érdekes tényre először G. Horváth Ákos (BME Geometria Tanszék) mutatott rá egyik 2000-ben írt publikációjában.

Természetesen adódhat a kérdés, hogy mi történik akkor, ha nem akarunk minden pontot meghatározni a négy távolsággal, hanem csak a $P_{1},P_{2},P_{3}$ és $P_{4}$ pontok által feszített tetraéderben található pontokra akarjuk ezt megtenni (háromszög a síkon). Erre a kérdésre a válasz csak 2016-ban született meg. Ez esetben nagy különbség van a sík és a három dimenziós tér között. A sík esetében az derül ki, hogy ha $X$ a $P_{1},P_{2}$ és $P_{3}$ által feszített háromszögön fekszik és a norma szigorúan konvex, akkor $X$ helyzete mindig pontosan meghatározható a $\large \|X-P_1\|$ , $\large \|X-P_2\|$ és $\large \|X-P_3\|$ távolságok ismeretében, illetve az állítás megfordítása is igaz (lásd a 6. ábrát). A térben viszont ez már nem így van! Pontosabban az derül ki, hogy ha a norma nem Euklideszi, akkor mindig található négy olyan $P_{1},P_{2},P_{3}$ és $P_{4}$ pont és két másik $X, X'$ pont, amelyek a négy pont által feszített tetraéderben vannak és teljesülnek a $\Vert X-P_{j}\Vert=\Vert X'-P_{j}\Vert$ egyenletek minden $j$ -re (lásd a 7. ábrát). Tehát általában egy tetraéderben fekvő pont helyzete nem határozható meg a csúcsoktól mért nem euklideszi távolságok ismeretében. A tétel bizonyítása a biszektorok geometriai vizsgálatán alapul, amely a háromdimenziós esetben projektív geometriai eszközöket kíván.

6. ábra. Ez csak akkor történhet meg, ha a norma nem szigorúan konvex. A színes szaggatott vonalak azt jelzik, hogy az adott távolságok megegyeznek.

Végül megjegyezzük, hogy a fenti problémák tárgyalása az általánosabb $n$ -dimenziós esetben is lehetséges, itt csupán a szemléletesség kedvéért szorítkoztunk a két-, illetve háromdimenziós esetekre.