Maximieren Delaunay-Triangulationen auf der Kugel den minimalen Winkel?

Delaunay-Triangulationen in der Ebene maximieren den minimalen Winkel in einem Dreieck. Gilt das auch für die Delaunay-Triangulation von Punkten auf der Kugel? (hier ist der "Winkel" der lokale Winkel in einer Nachbarschaft um den Scheitelpunkt an der Spitze).

Inspiriert von dieser Frage zu Math.SE.

cg.comp-geom delaunay-triangulation Suresh Venkat
quelle

Sicherlich würde die Eigenschaft für eine Menge gelten, die in einem kleinen, flachen Bereich der Kugel lokalisiert ist, da es sich um eine Mannigfaltigkeit handelt. Die eigentliche Frage wäre, ob die Eigenschaft geopfert wird, wenn sich die Punkte über die Kugel verteilen. Meine Vermutung wäre, dass Sie, um überhaupt eine Delaunay-Triangulation zu haben, noch mehr dicke Dreiecke benötigen würden als im euklidischen Fall, sodass die Eigenschaft gelten würde.

Josephine Moeller

Folgt dies dann nicht aus der Tatsache, dass die stereografische Projektion von einem generischen Punkt auf der Kugel Kreise auf Kreise abbildet und die Winkel zwischen sich überschneidenden Kurven (~ Kanten) aufgrund der Konformität beibehält? Oder fehlt mir etwas?

Jemand

@ Jemand Ja, das sollte es tun. Zumindest das meiste davon. Es mag ein oder zwei Probleme geben, aber das wäre die zentrale Idee. Ich habe mich darüber gewundert. Mir war nicht klar, dass die stereografische Zuordnung konform war.

Josephine Moeller

@ SureshVenkat Nun, da Sie den hyperbolischen Raum erwähnen, habe ich vielleicht meine Intuition rückwärts. Im hyperbolischen Raum muss berücksichtigt werden, dass es "illegale" Kreise gibt (dh Hyperzyklen und Horozyklen). Während Sie sich im kugelförmigen Raum befinden, tun Sie dies nicht. Sie können immer Kreise finden, die durch drei Punkte verlaufen.

Josephine Moeller

Ich denke nicht, dass das funktioniert. Sie möchten sicherstellen, dass die Projektion große Kreise zu Linien führt (da Sie die Winkel zwischen den Kanten der Dreiecke messen, bei denen es sich um große Kreise / Gerade handelt). Ich glaube nicht, dass man das mit einer stereografischen Projektion nicht machen kann. Sie können dies nur mit einer Projektion vom Punkt in der Mitte der Kugel tun, die einige Kreise zu Ellipsen führt.

Peter Shor

Antworten:

ERSTES ARGUMENT: Dies war meine erste Antwort. Beachten Sie, dass dieses Argument falsch ist. Siehe mein zweites Argument unten.

Ich denke nicht, dass es wahr ist. Der Grund, warum es in der Ebene funktioniert, ist, dass in einem Kreis der von einem Akkord umgebene Beschriftungswinkel die Hälfte des entsprechenden Mittelwinkels beträgt. Wenn wir also ein Dreieck mit einem kleinen Winkel haben, befinden sich alle Punkte, die mit der gegenüberliegenden Kante einen größeren Winkel bilden würden, innerhalb des leeren Delaunay-Kreises und gehören daher nicht zu den Punkten in der Konfiguration, für die wir eine Triangulation finden.

Angenommen, Sie haben eine Delaunay-Triangulation auf der Kugel. Platzieren Sie einen Punkt in der Mitte der Kugel und projizieren Sie alle Pionten auf eine Ebene. Die Kanten der Dreiecke (große Kreise auf der Kugel) werden alle zu Liniensegmenten genommen. Die Kreise, die die Eigenschaft des leeren Balls angeben, werden jedoch zu Ellipsen. Wenn sich also ein Punkt außerhalb der projizierten Ellipse, aber innerhalb des Kreises des Dreiecks befindet, würde dieser Punkt einen größeren Winkel mit der Kante bilden.

BEARBEITEN:

Warte eine Minute. Diese Antwort ist völlig falsch, da die zentrale Projektion keine Winkel beibehält. Ich denke immer noch, dass die Vermutung falsch ist, weil ich ein viel komplizierteres Argument habe, dass der Satz über eingeschriebene Winkel nicht für die Kugel gilt. Hier ist das Argument:

ZWEITES ARGUMENT:

Der Grund, warum dies in der Ebene gilt, ist, dass der von einem Akkord umgebene Beschriftungswinkel die Hälfte des entsprechenden Mittelwinkels beträgt. Dies gilt, weil im folgenden Diagramm und

C. Y. {X.}_{2} = \frac{1}{2} (π - - {X.}_{2} C. Y.)

$CYX_2 = \frac{1}{2} (\pi - X_2 C Y)$

Subtrahiert man

C. Y. {X.}_{1} = \frac{1}{2} (π - - {X.}_{1} C. Y.) .

$C Y X_1 = \frac{1}{2} (\pi - X_1 C Y).$

{X.}_{1} Y. {X.}_{2} = \frac{1}{2} {X.}_{1} C. {X.}_{2} .

$X_1 Y X_2 = \frac{1}{2} X_1 C X_2.$

Geometriebild

und

C. Y. {X.}_{2} = \frac{1}{2} (π - - {X.}_{2} C. Y. + EIN ({X.}_{2} C. Y.))

$CYX_2 = \frac{1}{2} ( \pi - X_2CY + A(X_2CY) \,)$

wobei

die Fläche des Dreiecks XYZ bedeutet. Subtrahieren wir

C. Y. {X.}_{1} = \frac{1}{2} (π - - {X.}_{1} C. Y. + EIN ({X.}_{1} C. Y.)),

$CYX_1 = \frac{1}{2} ( \pi - X_1CY + A(X_1CY) \,),$

A (X Y Z)

$A(XYZ)$

{X.}_{1} Y. {X.}_{2} = \frac{1}{2} ({X.}_{1} C. {X.}_{2} + EIN ({X.}_{2} C. Y.) - - EIN ({X.}_{1} C. Y.)) .

$X_1 Y X_2 = \frac{1}{2} (X_1 C X_2 + A(X_2CY) - A(X_1CY)\,).$

$Y$ $X_1YX_2$ $A(X_2CY) - A(X_1CY)$ $X_1X_2$ $A(XCY)$ $0$ $X$ $Y$ $X=Y$

$Y$ $X_1YX_2$ $X_1YX_2$ $Y'$ $X_1YX_2$ $X_1YX_2 < X_1 Y' X_2$

Peter Shor
quelle

Ich habe nicht erwartet, dass diese Frage so knifflig ist :). gespannt auf die Bilder.

Suresh Venkat