As triangulações de Delaunay na esfera maximizam o ângulo mínimo?

As triangulações de Delaunay no plano maximizam o ângulo mínimo em um triângulo. O mesmo vale para a triangulação de pontos de Delaunay na esfera? (aqui o "ângulo" é o ângulo local em uma vizinhança ao redor do vértice no ápice).

Inspirado, mas não relacionado a esta pergunta no Math.SE.

cg.comp-geom delaunay-triangulation Suresh Venkat
fonte

Certamente a propriedade seria válida para um conjunto localizado em uma região pequena e achatada da esfera, já que é uma variedade. A verdadeira questão seria se a propriedade é sacrificada à medida que os pontos se espalham pela esfera. Meu palpite seria que, para ter uma triangulação de Delaunay, você precisaria de triângulos gordos ainda mais do que no caso euclidiano, para que a propriedade se sustentasse.

Josephine Moeller

Isso não decorre, portanto, do fato de que a projeção estereográfica de um ponto genérico na esfera mapeia círculos em círculos e preserva os ângulos entre as curvas que se cruzam (arestas) devido à conformidade? Ou eu estou esquecendo de alguma coisa?

alguem

@ alguém Sim, isso deve ser feito. Pelo menos a maior parte. Pode haver um problema ou dois, mas essa seria a idéia central. Eu estava me perguntando sobre isso. Não percebi que o mapeamento estereográfico era conforme.

Josephine Moeller

@SureshVenkat Agora que você mencionou o espaço hiperbólico, talvez eu tenha minha intuição para trás. No espaço hiperbólico, você deve levar em consideração o fato de que existem circuitos "ilegais" (por exemplo, hiper-motocicletas e horociclos). Enquanto no espaço esférico você não; você sempre pode encontrar círculos que passam por três pontos.

Josephine Moeller

Eu não acho que isso funciona. Você quer ter certeza de que a projeção leva grandes círculos às linhas (já que você está medindo os ângulos entre as arestas dos triângulos, que são grandes círculos / retos). Não acho que você não possa fazer isso com uma projeção estereográfica. Você só pode fazer isso com uma projeção a partir do ponto no centro da esfera, que leva alguns círculos às elipses.

Peter Shor

PRIMEIRO ARGUMENTO: Esta foi minha primeira resposta. Observe que esse argumento está errado. Veja meu segundo argumento abaixo.

Eu não acho que é verdade. A razão pela qual ele trabalha no plano é que, em um círculo, o ângulo inscrito subtendido por um acorde é metade do ângulo central correspondente. Assim, se tivermos um triângulo com um ângulo pequeno, todos os pontos que formariam um ângulo maior com a aresta oposta estarão dentro do círculo vazio de Delaunay e, portanto, não são um dos pontos na configuração da qual estamos encontrando uma triangulação.

Agora, suponha que você tenha uma triangulação de Delaunay na esfera. Coloque um ponto no centro da esfera e projete todos os pioneiros em um plano. As arestas dos triângulos (grandes círculos na esfera) são levadas para segmentos de linha. Mas os círculos que dão a propriedade da bola vazia são levados às elipses; portanto, se houver um ponto fora da elipse projetada, mas dentro do circulo do triângulo, esse ponto faria um ângulo maior com a aresta.

EDITAR:

Espere um minuto. Esta resposta está completamente errada, porque a projeção central não preserva ângulos. Ainda acho que a conjectura está errada, porque tenho um argumento muito mais complicado de que o teorema dos ângulos inscritos não se sustenta na esfera. Aqui está o argumento:

SEGUNDO ARGUMENTO:

A razão disso no plano é que o ângulo inscrito subtendido por um acorde é metade do ângulo central correspondente. Isso vale porque, no diagrama abaixo, temos e

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

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

Subtraindo, obtemos

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 1} Y X_{2} = \frac{1 1}{2} X_{1 1} C X_{2} .

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

imagem geometria

C Y X_{2} = \frac{1}{2} (π - X_{2} C Y + A (X_{2} C Y))

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

C Y X_{1} = \frac{1}{2} (π - X_{1} C Y + A (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 1} C X_{2} + UMA (X_{2} C Y) - UMA (X_{1 1} C Y)) .

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

Para o lugar geométrico dos pontos $Y$ fazendo um ângulo constante $X_1YX_2$ Para ser um círculo, precisamos, portanto, que a diferença de áreas $A(X_2CY) - A(X_1CY)$ depende apenas do comprimento do arco $X_1X_2$ . No entanto, isso é incompatível com a observação de que $A(XCY)$ é $0$ para $X$ diametralmente oposto $Y$ e para $X=Y$ , mas cresce para um tamanho máximo intermediário.

Assim, o lócus de pontos $Y$ com ângulo constante $X_1YX_2$ não é um círculo. Isso significa que, para algum triângulo $X_1YX_2$ podemos encontrar um ponto $Y'$ fora do circulo de $X_1YX_2$ então o ângulo $X_1YX_2 < X_1 Y' X_2$ . Podemos então usar isso para construir um contra-exemplo da conjectura de que as triangulações de Delaunay na esfera maximizam o ângulo mínimo.

Peter Shor
fonte

Eu não esperava que essa pergunta fosse tão complicada :). aguardando ansiosamente as fotos.

precisa

As triangulações de Delaunay na esfera maximizam o ângulo mínimo?

Respostas: