Dehnungsfaktor - Stretch factor

Der Dehnungsfaktor einer Einbettung misst den Faktor, um den die Einbettung Entfernungen verzerrt . Angenommen, ein Metrikraum S ist durch eine Metrikkarte in einen anderen Metrikraum T eingebettet , eine kontinuierliche Eins-zu-Eins-Funktion f , die den Abstand zwischen jedem Punktpaar beibehält oder verringert. Dann gibt die Einbettung zu zwei verschiedenen Begriffen des Abstandes zwischen Paaren von Punkten in S . Jedes Punktpaar ( x , y ) in S hat sowohl einen Eigenabstand als auch den Abstand von x bis y in S , und einem kleineren extrinsischen Abstand, der Abstand von f ( x ) zu f ( y ) in T . Der Dehnungsfaktor des Paares ist das Verhältnis zwischen diesen beiden Abständen d ( f ( x ), f ( y )) / d ( x , y ) . Der Dehnungsfaktor der gesamten Abbildung ist das Supremum (falls vorhanden) der Dehnungsfaktoren aller Punktpaare. Der Dehnungsfaktor wurde auch als Verzerrung oder Erweiterung der Abbildung bezeichnet.

Der Dehnungsfaktor ist wichtig in der Theorie der geometrischen Schraubenschlüssel , gewichteten Graphen , die die euklidischen Abstände zwischen einer Reihe von Punkten in der euklidischen Ebene approximieren . In diesem Fall ist die eingebettete Metrik S ein endlicher metrischer Raum, dessen Abstände die kürzesten Pfadlängen in einem Graphen sind, und die Metrik T, in die S eingebettet ist, ist die euklidische Ebene. Wenn das Diagramm und seine Einbettung festgelegt sind, die Kantengewichte des Diagramms jedoch variieren können, wird der Dehnungsfaktor minimiert, wenn die Gewichte genau den euklidischen Abständen zwischen den Kantenendpunkten entsprechen. Die Forschung in diesem Bereich hat sich darauf konzentriert, spärliche Graphen für einen bestimmten Punktsatz mit niedrigem Dehnungsfaktor zu finden.

Das Johnson-Lindenstrauss-Lemma behauptet, dass jeder endliche metrische Raum mit n Punkten in einen euklidischen Raum der Dimension O (log  n ) mit Verzerrung 1 + ε für jede Konstante ε > 0 eingebettet werden kann , wobei der konstante Faktor in der O- Notation hängt von der Wahl von  ε ab . Dieses Ergebnis und verwandte Methoden zur Konstruktion verzerrungsarmer metrischer Einbettungen sind in der Theorie der Approximationsalgorithmen wichtig . Ein großes offenes Problem in diesem Bereich ist die GNRS-Vermutung , die (falls zutreffend) die Familien von Graphen, die Einbettungen mit begrenzter Dehnung in Räume aufweisen, als alle geringfügig geschlossenen Graphfamilien charakterisieren würde .

In der Knotentheorie ist die Verzerrung eines Knotens eine Knoteninvariante , der minimale Dehnungsfaktor jeder Einbettung des Knotens als Raumkurve in den euklidischen Raum . Der Bachelor-Forscher John Pardon gewann den Morgan-Preis 2012 für seine Forschung, die zeigt, dass es keine Obergrenze für die Verzerrung von Torusknoten gibt, was ein ursprünglich von Mikhail Gromov aufgeworfenes Problem löst .

In der Untersuchung des kurvenverkürzenden Flusses , bei dem sich jeder Punkt einer Kurve in der euklidischen Ebene senkrecht zur Kurve bewegt und dessen Geschwindigkeit proportional zur lokalen Krümmung ist, hat Huisken (1998) bewiesen, dass der Dehnungsfaktor jeder einfachen geschlossenen glatten Kurve (mit intrinsischen Abständen gemessen durch Bogenlänge) ändert sich monoton. Insbesondere nimmt bei jedem Paar ( x , y ) , das ein lokales Maximum des Dehnungsfaktors bildet, der Dehnungsfaktor streng ab, außer wenn die Kurve ein Kreis ist. Diese Eigenschaft wurde später verwendet, um den Beweis des Gage-Hamilton-Grayson-Theorems zu vereinfachen, wonach jede einfache geschlossene glatte Kurve einfach und glatt bleibt, bis sie zu einem Punkt zusammenfällt und zuvor in ihrer Form zu einem Kreis konvergiert.

Verweise