Distanzgeometrie - Distance geometry

Distanzgeometrie ist die Charakterisierung und Untersuchung von Punktmengen, die nur auf gegebenen Werten der Distanzen zwischen Stabpaaren basieren . Abstrakter ist es das Studium semimetrischer Räume und der isometrischen Transformationen zwischen ihnen. Aus dieser Sicht kann es als ein Thema innerhalb der allgemeinen Topologie betrachtet werden .

Historisch gesehen ist das erste Ergebnis der Distanzgeometrie die Formel von Heron im 1. Jahrhundert n. Chr. Die moderne Theorie begann im 19. Jahrhundert mit Arbeiten von Arthur Cayley , gefolgt von umfangreicheren Entwicklungen im 20. Jahrhundert von Karl Menger und anderen.

Distanzgeometrieprobleme treten immer dann auf, wenn man die Form einer Konfiguration von Punkten ( relative Positionen ) aus den Abständen zwischen ihnen ableiten muss, wie in der Biologie , Sensornetzen , Vermessung , Navigation , Kartographie und Physik .

Einführung und Definitionen

Die Konzepte der Distanzgeometrie werden zunächst durch die Beschreibung zweier besonderer Probleme erläutert.

Erstes Problem: Hyperbolische Navigation

Betrachten Sie drei Bodenfunkstationen A, B, C, deren Standorte bekannt sind. Ein Funkempfänger befindet sich an einem unbekannten Ort. Die Zeiten, die ein Funksignal von den Stationen zum Empfänger benötigt, , sind unbekannt, aber die Zeitunterschiede, und , sind bekannt. Aus ihnen kennt man die Entfernungsunterschiede und , aus denen die Position des Empfängers ermittelt werden kann. ${\displaystyle t_{A},t_{B},t_{C}}$${\displaystyle t_{A}-t_{B}}$${\displaystyle t_{A}-t_{C}}$${\displaystyle c(t_{A}-t_{B})}$${\displaystyle c(t_{A}-t_{C})}$

Zweites Problem: Dimensionsreduktion

Bei der Datenanalyse erhält man oft eine Liste von Daten, die als Vektoren dargestellt werden , und man muss herausfinden, ob sie innerhalb eines niederdimensionalen affinen Unterraums liegen. Eine niedrigdimensionale Darstellung von Daten hat viele Vorteile, wie z. B. die Einsparung von Speicherplatz, Rechenzeit und einen besseren Einblick in die Daten. ${\displaystyle \mathbf{v} =(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}}$

Definitionen

Nun formalisieren wir einige Definitionen, die sich natürlich aus der Betrachtung unserer Probleme ergeben.

Semimetrischer Raum

Bei einer Liste von Punkten auf , können wir die Abstände zwischen Punktpaaren durch eine Liste von , beliebig angeben . Dies definiert einen semimetrischen Raum : einen metrischen Raum ohne Dreiecksungleichung . ${\displaystyle R=\{P_{0},\ldots ,P_{n}\}}$${\displaystyle n\geq 0}$${\displaystyle d_{ij}>0}$${\displaystyle 0\leq i<j\leq n}$

Explizit Wir definieren einen semimetric Raum als nicht leeren Satz mit einem semimetric ausgestattet , so daß für alle , ${\displaystyle R}$${\displaystyle d:R\times R\to [0,\infty )}$${\displaystyle x,y\in R}$

1. Positivität:   wenn und nur wenn   .${\displaystyle d(x,y)=0}$${\displaystyle x=y}$
2. Symmetrie: .${\displaystyle d(x,y)=d(y,x)}$

Jeder metrische Raum ist erst recht ein semimetrischer Raum. Insbesondere ist der -dimensionale euklidische Raum der kanonische metrische Raum in der Distanzgeometrie. ${\displaystyle \mathbb{R} ^{k}}$${\displaystyle k}$

Die Dreiecksungleichung wird in der Definition weggelassen, weil wir den Abständen nicht mehr Beschränkungen auferlegen wollen als die bloße Voraussetzung, dass sie positiv sind. ${\displaystyle d_{ij}}$

In der Praxis entstehen semimetrische Räume natürlich aus ungenauen Messungen. Wenn beispielsweise drei Punkte auf einer Linie mit angegeben sind , könnte eine ungenaue Messung ergeben , die die Dreiecksungleichung verletzt. ${\displaystyle A,B,C}$${\displaystyle d_{AB}=1,d_{BC}=1,d_{AC}=2}$${\displaystyle d_{AB}=0.99,d_{BC}=0.98,d_{AC}=2.00}$

Isometrische Einbettung

Bei zwei semimetrischen Räumen, , ist eine isometrische Einbettung von bis eine Abbildung , die die semimetrische, dh für alle , beibehält . ${\displaystyle (R,d),(R',d')}$${\displaystyle R}$${\displaystyle R'}$${\displaystyle f:R\to R'}$${\displaystyle x,y\in R}$${\displaystyle d(x,y)=d'(f(x),f(y))}$

Zum Beispiel, wenn der oben definierte endliche semimetrische Raum gegeben ist, wird eine isometrische Einbettung in durch Punkte definiert , so dass für alle . ${\displaystyle (R,d)}$${\textstyle A_{0},A_{1},\ldots,A_{n}\in\mathbb{R}^{k}}$${\displaystyle d(A_{i},A_{j})=d_{ij}}$${\displaystyle 0\leq i<j\leq n}$

Affine Unabhängigkeit

In Anbetracht der Punkte , werden sie definiert sein affin unabhängig , genau dann , wenn sie nicht in einem einzigen passen -dimensionalen affinen Unterraum , für alle , genau dann , wenn die - Simplex sie überspannen , positiv hat -Volumen, das heißt . ${\textstyle A_{0},A_{1},\ldots,A_{n}\in\mathbb{R}^{k}}$${\displaystyle l}$${\displaystyle \mathbb{R} ^{k}}$${\displaystyle \ell <n}$${\displaystyle n}$${\displaystyle v_{n}}$${\displaystyle n}$${\displaystyle \operatorname {Vol} _{n}(v_{n})>0}$

Im Allgemeinen sind sie affin unabhängig, da ein generischer n- Simplex nicht entartet ist. Zum Beispiel sind 3 Punkte in der Ebene im Allgemeinen nicht kollinear, da das Dreieck, das sie aufspannen, nicht zu einem Liniensegment degeneriert. Ebenso sind 4 Punkte im Raum im Allgemeinen nicht koplanar, da das Tetraeder, das sie aufspannen, nicht in ein flaches Dreieck entartet. ${\displaystyle k\geq n}$

Wann müssen sie affin abhängig sein. Dies kann daran gesehen werden, dass jeder -simplex, der hineinpasst , "flach" sein muss. ${\displaystyle n>k}$${\displaystyle n}$${\displaystyle \mathbb{R} ^{k}}$

Cayley-Menger-Determinanten

Cayley-Menger-Determinanten , benannt nach Arthur Cayley und Karl Menger, sind Determinanten von Abstandsmatrizen zwischen Punktmengen.

Lassen Sie werden n  + 1 Punkten in einem Raum semimetric, ihre Cayleys-Menger Determinante definiert durch ${\textstyle A_{0},A_{1},\ldots ,A_{n}}$

${\displaystyle \operatorname {CM} (A_{0},\cdots ,A_{n})={\begin{vmatrix}0&d_{01}^{2}&d_{02}^{2}&\cdots &d_{ 0n}^{2}&1\\d_{01}^{2}&0&d_{12}^{2}&\cdots &d_{1n}^{2}&1\\d_{02}^{2}&d_{12 }^{2}&0&\cdots &d_{2n}^{2}&1\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\d_{0n}^{2}&d_{1n} ^{2}&d_{2n}^{2}&\cdots &0&1\\1&1&1&\cdots &1&0\end{vmatrix}}}$

Wenn , dann bilden sie die Eckpunkte eines (möglicherweise entarteten ) n- Simplex in . Es kann gezeigt werden, dass das n- dimensionale Volumen des Simplex erfüllt ${\textstyle A_{0},A_{1},\ldots,A_{n}\in\mathbb{R}^{k}}$${\displaystyle v_{n}}$${\displaystyle \mathbb{R} ^{k}}$${\displaystyle v_{n}}$

${\displaystyle \operatorname {Vol} _{n}(v_{n})^{2}={\frac {(-1)^{n+1}}{(n!)^{2}2^{ n}}}\operatorname {CM} (A_{0},\ldots ,A_{n}).}$

Beachten Sie, dass wir für den Fall von haben , was bedeutet, dass das "0-dimensionale Volumen" eines 0-Simplex 1 ist, dh es gibt 1 Punkt in einem 0-Simplex. ${\displaystyle n=0}$${\displaystyle \operatorname {Vol} _{0}(v_{0})=1}$

${\textstyle A_{0},A_{1},\ldots ,A_{n}}$sind affin unabhängig , d. h. . Somit bieten Cayley-Menger-Determinanten eine rechnerische Möglichkeit, die affine Unabhängigkeit zu beweisen. ${\displaystyle \operatorname {Vol} _{n}(v_{n})>0}$${\displaystyle (-1)^{n+1}\operatorname {CM} (A_{0},\ldots ,A_{n})>0}$

Wenn , dann müssen die Punkte affin abhängig sein, also . Cayleys Aufsatz aus dem Jahr 1841 untersuchte den Spezialfall von , dh alle fünf Punkte im dreidimensionalen Raum müssen haben . ${\displaystyle k<n}$${\displaystyle \operatorname {CM} (A_{0},\ldots ,A_{n})=0}$${\displaystyle k=3,n=4}$${\displaystyle A_{0},\ldots ,A_{4}}$${\displaystyle \operatorname {CM} (A_{0},\ldots ,A_{4})=0}$

Geschichte

Das erste Ergebnis der Abstandsgeometrie ist die Formel von Heron aus dem 1. Jahrhundert n. Chr., die die Fläche eines Dreiecks aus den Abständen zwischen seinen 3 Eckpunkten angibt. Brahmaguptas Formel aus dem 7. Jahrhundert n. Chr. verallgemeinert sie auf zyklische Vierecke . Tartaglia , aus dem 16. Jahrhundert n. Chr., verallgemeinerte es, um das Volumen des Tetraeders aus den Abständen zwischen seinen 4 Scheitelpunkten anzugeben.

Die moderne Theorie der Distanzgeometrie begann mit Authur Cayley und Karl Menger . Cayley veröffentlichte 1841 die Cayley-Determinante, die ein Sonderfall der allgemeinen Cayley-Menger-Determinante ist. Menger bewies 1928 einen Charakterisierungssatz aller semimetrischen Räume, die isometrisch in den n- dimensionalen euklidischen Raum einbettbar sind . 1931 verwendete Menger Abstandsbeziehungen, um eine axiomatische Behandlung der euklidischen Geometrie zu geben. ${\displaystyle \mathbb{R} ^{n}}$

Das Buch von Leonard Blumenthal gibt einen allgemeinen Überblick zur Distanzgeometrie auf Graduiertenebene, von dem ein Großteil zum Zeitpunkt seiner Veröffentlichung erstmals in englischer Sprache behandelt wird.

Menger-Charakterisierungssatz

Menger bewies den folgenden Charakterisierungssatz von semimetrischen Räumen:

Ein semimetrischer Raum ist isometrisch in den -dimensionalen euklidischen Raum einbettbar , aber nicht in einen , genau dann, wenn: ${\displaystyle (R,d)}$${\displaystyle n}$${\displaystyle \mathbb{R} ^{n}}$${\displaystyle \mathbb{R} ^{m}}$${\displaystyle 0\leq m<n}$

1. ${\displaystyle R}$enthält eine -Punkt Teilmenge , die mit einer unabhängigen affin isometrisch -Punkt Teilmenge von ;${\displaystyle (n+1)}$${\displaystyle S}$${\displaystyle (n+1)}$${\displaystyle \mathbb{R} ^{n}}$
2. Jede -Punkt-Teilmenge , die durch Hinzufügen von zwei beliebigen zusätzlichen Punkten von zu erhalten wird , ist kongruent zu einer -Punkt-Teilmenge von .${\displaystyle (n+3)}$${\displaystyle S'}$${\displaystyle R}$${\displaystyle S}$${\displaystyle (n+3)}$${\displaystyle \mathbb{R} ^{n}}$

Ein Beweis dieses Satzes in leicht abgeschwächter Form (für metrische Räume statt semimetrische Räume) ist in.

Charakterisierung über Cayley-Menger-Determinanten

Die folgenden Ergebnisse sind in Blumethals Buch bewiesen.

Einbetten von Punkten in${\displaystyle n+1}$${\displaystyle \mathbb{R} ^{n}}$

Gegeben einen semimetrischen Raum mit , und , , ist eine isometrische Einbettung von in durch definiert , so dass für alle . ${\displaystyle (S,d)}$${\displaystyle S=\{P_{0},\ldots ,P_{n}\}}$${\displaystyle d(P_{i},P_{j})=d_{ij}\geq 0}$${\displaystyle 0\leq i<j\leq n}$${\displaystyle (S,d)}$${\displaystyle \mathbb{R} ^{n}}$${\textstyle A_{0},A_{1},\ldots,A_{n}\in\mathbb{R}^{n}}$${\displaystyle d(A_{i},A_{j})=d_{ij}}$${\displaystyle 0\leq i<j\leq n}$

Auch hier stellt sich die Frage, ob es eine solche isometrische Einbettung für gibt . ${\displaystyle (S,d)}$

Eine notwendige Bedingung ist leicht zu sehen: für alle , lassen Sie das sein k durch Simplex gebildet , dann ${\displaystyle k=1,\ldots,n}$${\displaystyle v_{k}}$${\textstyle A_{0},A_{1},\ldots ,A_{k}}$

${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})=(-1)^{k+1}\operatorname {CM} (A_ {0},\ldots ,A_{k})=2^{k}(k!)^{k}\operatorname {Vol} _{k}(v_{k})^{2}\geq 0}$

Das Umgekehrte gilt auch. Das heißt, wenn für alle , ${\displaystyle k=1,\ldots,n}$

${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0,}$

dann existiert eine solche Einbettung.

Darüber hinaus ist eine solche Einbettung bis auf die Isometrie in . Das heißt, bei gegebenen zwei isometrischen Einbettungen, die durch , und definiert sind , existiert eine (nicht unbedingt eindeutige) Isometrie , so dass für alle . Solche sind genau dann eindeutig, wenn , d. h. affin unabhängig sind. ${\displaystyle \mathbb{R} ^{n}}$${\textstyle A_{0},A_{1},\ldots ,A_{n}}$${\textstyle A'_{0},A'_{1},\ldots ,A'_{n}}$${\displaystyle T:\mathbb{R}^{n}\to\mathbb{R}^{n}}$${\displaystyle T(A_{k})=A'_{k}}$${\displaystyle k=0,\ldots,n}$${\displaystyle T}$${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n})\neq 0}$${\textstyle A_{0},A_{1},\ldots ,A_{n}}$

Einbettung und Punkte${\displaystyle n+2}$${\displaystyle n+3}$

Wenn Punkte in as eingebettet werden können , dann ist außer den oben genannten Bedingungen eine zusätzliche notwendige Bedingung, dass der durch gebildete -Simplex kein -dimensionales Volumen haben darf . Das heißt, . ${\displaystyle n+2}$${\displaystyle P_{0},\ldots ,P_{n+1}}$${\displaystyle \mathbb{R} ^{n}}$${\displaystyle A_{0},\ldots ,A_{n+1}}$${\displaystyle (n+1)}$${\textstyle A_{0},A_{1},\ldots ,A_{n+1}}$${\displaystyle (n+1)}$${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0}$

Das Umgekehrte gilt auch. Das heißt, wenn für alle , ${\displaystyle k=1,\ldots,n}$

${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0,}$

und

${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0,}$

dann existiert eine solche Einbettung.

Für Einbettungspunkte in sind die notwendigen und ausreichenden Bedingungen ähnlich: ${\displaystyle n+3}$${\displaystyle \mathbb{R} ^{n}}$

1. Für alle , ;${\displaystyle k=1,\ldots,n}$${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0}$
2. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0;}$
3. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+2})=0;}$
4. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1},P_{n+2})=0.}$

Beliebig viele Punkte einbetten

Der Fall erweist sich im Allgemeinen als ausreichend. ${\displaystyle n+3}$

Im Allgemeinen ist ein semimetric Raum gegeben , kann es isometrisch eingebettet sein , wenn und nur wenn es vorhanden ist , so dass für alle , und für jede , ${\displaystyle (R,d)}$${\displaystyle \mathbb{R} ^{n}}$${\displaystyle P_{0},\ldots,P_{n}\in R}$${\displaystyle k=1,\ldots,n}$${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0}$${\displaystyle P_{n+1},P_{n+2}\in R}$

1. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0;}$
2. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+2})=0;}$
3. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1},P_{n+2})=0.}$

Und eine solche Einbettung ist bis auf die Isometrie in . ${\displaystyle \mathbb{R} ^{n}}$

Wenn , dann kann es nicht isometrisch in irgendeine eingebettet werden . Und eine solche Einbettung ist einzigartig bis hin zur einzigartigen Isometrie in . ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n})\neq 0}$${\displaystyle \mathbb{R}^{m},m<n}$${\displaystyle \mathbb{R} ^{n}}$

Somit bieten Cayley-Menger-Determinanten einen konkreten Weg, um zu berechnen, ob ein semimetrischer Raum in ein endliches eingebettet werden kann , und wenn ja, was ist das minimale . ${\displaystyle \mathbb{R} ^{n}}$${\displaystyle n}$${\displaystyle n}$

Anwendungen

Es gibt viele Anwendungen der Distanzgeometrie.

In Telekommunikationsnetzen wie GPS sind die Positionen einiger Sensoren bekannt (die Anker genannt werden) und einige der Abstände zwischen den Sensoren sind ebenfalls bekannt: Das Problem besteht darin, die Positionen für alle Sensoren zu identifizieren. Hyperbolische Navigation ist eine Pre-GPS-Technologie, die Distanzgeometrie zur Ortung von Schiffen basierend auf der Zeit verwendet, die Signale benötigen, um Anker zu erreichen.

In der Chemie gibt es viele Anwendungen. Techniken wie NMR können Abstände zwischen Atompaaren eines gegebenen Moleküls messen, und das Problem besteht darin, aus diesen Abständen auf die dreidimensionale Form des Moleküls zu schließen.

Einige Softwarepakete für Anwendungen sind:

• DGSOL . Löst Geometrieprobleme mit großen Distanzen bei der makromolekularen Modellierung .
• Xplor-NIH . Basierend auf X-PLOR , um die Struktur von Molekülen anhand von Daten aus NMR-Experimenten zu bestimmen. Es löst Distanzgeometrieprobleme mit heuristischen Methoden (wie simuliertes Annealing ) und lokalen Suchmethoden (wie konjugierte Gradientenminimierung ).
• TINKER . Molekulare Modellierung und Design. Es kann Distanzgeometrieprobleme lösen.
• SNLSDPclique . MATLAB-Code zur Ortung von Sensoren in einem Sensornetzwerk anhand der Abstände zwischen den Sensoren.

Siehe auch

• Euklidische Distanzmatrix
• Mehrdimensionale Skalierung (eine statistische Technik, die verwendet wird, wenn Entfernungen mit zufälligen Fehlern gemessen werden)
• metrischer Raum
• Tartaglias Formel
• Triangulation
• Trilateration

Verweise