Czy triangulacje Delaunaya na sferze maksymalizują minimalny kąt?

Triangulacje Delaunaya w płaszczyźnie maksymalizują minimalny kąt w trójkącie. Czy to samo dotyczy triangulacji punktów w kuli ziemskiej przez Delaunaya? (tutaj „kąt” to kąt lokalny w sąsiedztwie wierzchołka na wierzchołku).

Zainspirowany, ale niezwiązany z tym pytaniem na Math.SE.

cg.comp-geom delaunay-triangulation Suresh Venkat
źródło

Z pewnością ta właściwość byłaby odpowiednia dla zestawu zlokalizowanego w małym, spłaszczonym regionie kuli, ponieważ jest ona różnorodna. Prawdziwe pytanie brzmiałoby, czy własność jest poświęcana, gdy punkty rozprzestrzeniają się po kuli. Domyślam się, że do triangulacji Delaunaya potrzebne byłyby przede wszystkim grube trójkąty jeszcze bardziej niż w przypadku euklidesowym, więc własność się utrzymałaby.

Josephine Moeller,

Czy nie wynika to zatem z faktu, że projekcja stereograficzna z ogólnego punktu na kuli odwzorowuje koła na okręgi i zachowuje kąty między przecinającymi się krzywymi (~ krawędziami) ze względu na zgodność? A może coś mi brakuje?

ktoś

@ ktoś tak, powinien to zrobić. Przynajmniej większość. Może być jakiś haczyk lub dwa, ale to byłby główny pomysł. Zastanawiałem się nad tym. Nie zdawałem sobie sprawy, że mapowanie stereograficzne jest zgodne.

Josephine Moeller,

@SureshVenkat Teraz, kiedy wspominasz o przestrzeni hiperbolicznej, być może mam intuicję do tyłu. W przestrzeni hiperbolicznej należy wziąć pod uwagę fakt, że istnieją „nielegalne” koła (tj. Hiperocykle i motocykle). W przestrzeni sferycznej nie ma; zawsze możesz znaleźć kręgi przechodzące przez trzy punkty.

Josephine Moeller,

Nie sądzę, że to działa. Chcesz się upewnić, że rzut ma wielkie koła do linii (ponieważ mierzysz kąty między krawędziami trójkątów, które są dużymi okręgami / prostymi). Nie sądzę, że nie można tego zrobić za pomocą projekcji stereograficznej. Możesz to zrobić tylko z rzutem z punktu w środku kuli, który powoduje elipsy niektórych okręgów.

Peter Shor,

PIERWSZY ARGUMENT: To była moja pierwsza odpowiedź. Zauważ, że ten argument jest błędny. Zobacz mój drugi argument poniżej.

Nie sądzę, że to prawda. Powodem, dla którego działa on w płaszczyźnie, jest to, że w okręgu wpisany kąt cięciwy stanowi połowę odpowiedniego kąta środkowego. Tak więc, jeśli mamy trójkąt o małym kącie, wszelkie punkty, które zrobiłyby większy kąt z przeciwną krawędzią, znajdują się wewnątrz pustego okręgu Delaunay, a zatem nie są jednym z punktów w konfiguracji, w której znajdujemy triangulację.

Załóżmy, że masz triangulację Delaunaya na kuli. Umieść punkt w środku kuli i rzutuj wszystkie pionki na płaszczyznę. Krawędzie trójkątów (wielkie koła na kuli) są przenoszone do segmentów linii. Ale koła, które nadają właściwość pustej kuli, są przenoszone na elipsy, a więc jeśli na zewnątrz rzutowanej elipsy znajduje się punkt, ale wewnątrz okręgu trójkąta, punkt ten utworzyłby większy kąt z krawędzią.

EDYTOWAĆ:

Poczekaj minutę. Ta odpowiedź jest całkowicie błędna, ponieważ środkowa projekcja nie zachowuje kątów. Nadal uważam, że domniemanie jest błędne, ponieważ mam o wiele bardziej skomplikowany argument, że twierdzenie o wpisanych kątach nie trzyma się kuli. Oto argument:

DRUGI ARGUMENT:

Powodem tego jest to, że kąt wpisany w cięciwę stanowi połowę odpowiedniego kąta środkowego. Dzieje się tak, ponieważ na poniższym schemacie mamy

do Y X_{2)} = \frac{1}{2)} (π - X_{2)} do Y)

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

do Y X_{1} = \frac{1}{2)} (π - X_{1} do Y) .

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

X_{1} Y X_{2)} = \frac{1}{2)} X_{1} do X_{2)} .

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

obraz geometrii

Teraz w geometrii sferycznej otrzymujemy

do Y X_{2)} = \frac{1}{2)} (π - X_{2)} do Y + ZA (X_{2)} do Y))

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

do Y X_{1} = \frac{1}{2)} (π - X_{1} do Y + ZA (X_{1} do Y)),

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

A (X Y Z)

$A(XYZ)$ oznacza obszar trójkąta XYZ. Odejmujemy, rozumiemy

X_{1} Y X_{2)} = \frac{1}{2)} (X_{1} do X_{2)} + ZA (X_{2)} do Y) - ZA (X_{1} do Y)) .

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

Dla umiejscowienia punktów $Y$ tworząc stały kąt $X_1YX_2$ aby być kołem, potrzebujemy zatem różnicy obszarów $A(X_2CY) - A(X_1CY)$ zależy tylko od długości łuku $X_1X_2$ . Jest to jednak niezgodne z tą obserwacją $A(XCY)$ jest $0$ dla $X$ diametralnie przeciwnie $Y$ i dla $X=Y$ , ale rośnie do pewnego maksymalnego rozmiaru pomiędzy.

Zatem miejsce punktów $Y$ ze stałym kątem $X_1YX_2$ nie jest kołem. Oznacza to, że dla niektórych trójkątów $X_1YX_2$ możemy znaleźć punkt $Y'$ poza okręgiem $X_1YX_2$ więc kąt $X_1YX_2 < X_1 Y' X_2$ . Możemy następnie użyć tego do zbudowania kontrprzykładu do przypuszczenia, że triangulacje Delaunaya na sferze maksymalizują minimalny kąt.

Peter Shor
źródło

Nie spodziewałem się, że to pytanie będzie takie trudne :). z niecierpliwością czekam na zdjęcia.

Suresh Venkat,

Czy triangulacje Delaunaya na sferze maksymalizują minimalny kąt?

Odpowiedzi: