Enumeração de gráficos derivados de mosaicos de Delaunay em 3D

12

Existe um algoritmo que enumera os gráficos que correspondem a algum mosaico de pontos de Delaunay em 3D?

Em caso afirmativo, existe uma parametrização eficiente de geometrias que correspondem a qualquer "gráfico de Delaunay"?

Eu estou procurando enumerar sistematicamente todas as geometrias estáveis ​​de moléculas de uma composição especificada sem nenhum conhecimento a priori de ligação etc.

EDIT: Seja o conjunto de gráficos com N vértices. Seja D : R 3 NG N um mapa de N pontos em para um gráfico correspondente a um mosaico de Delaunay dos referidos pontos em 3D.GNND:R3NGNNR3

Como enumerar (eficientemente)?D(R3N)

Além disso, dado um gráfico , como posso parametrizar (eficientemente)?D - 1 ( g )gGnD1(g)

EDIT: Exemplo em 2D: Para 4 pontos, existem 2 gráficos Delaunay.

123|4 and 12|×|34

Ou mostrado de maneira explicitamente plana:

Gráficos 2D delaunay para 4 pontos

O primeiro desses gráficos pode ser parametrizado por qualquer posição dos pontos 1, 2 e 4, ou seja, , enquanto o ponto 3 seria qualquer ponto que é maior que o raio de o círculo que circunscreve os pontos 1, 2 e 4 centralizados em e é a posição do ponto . x 3 (R,θ)=C( x 1 , x 2 , x 4 )+r ( cos ( θ ) sin ( θ ) ) rC( x 1 , x 2 , x 4 ) x i iR3×3x3(r,θ)=c(x1,x2,x4)+r(cos(θ)sin(θ))rc(x1,x2,x4)xii

Último folego
fonte
O que você quer dizer com "parametrização eficiente de geometrias". Também não sou químico, então o que significa "geometrias estáveis ​​de moléculas de uma composição especificada"? Com um pouco mais de esclarecimento, isso pode ser facilmente respondido.
Gareth A. Lloyd
Para pontos na posição geral em 3D, existem graus de liberdade independentes ( para o centro de massa e outros 3 graus para os principais eixos de rotação). Cada conjunto possui algum mosaico de Delaunay. Gostaria de inverter esse processo: dado um mosaico de Delaunay, quero uma parametrização de todos os conjuntos de pontos que levem a esse mosaico de Delaunay. Uma geometria estável é um conjunto de pontos no espaço com pesos positivos associados para os quais a energia funcional é localmente mínima. 3 N - 6 3 N - 3 N NN3N63N3NN
Death Breath
Você está pedindo para encontrar todas as possíveis triangulações de Delaunay? Você pode esclarecer um pouco? Você define uma recompensa por isso, mas sinto que a pergunta ainda não está clara para muitos.
Szabolcs
@Szabolcs: Espero que a edição esclareça o problema.
Death Breath
@ Deathbreath um pouco ... entendo direito que você precisa encontrar todos os gráficos que possam corresponder a uma triangulação de Delaunay de algum conjunto de pontos em 3D? Você pode dar um exemplo específico? Por exemplo, em 2D para 4 pontos, os gráficos que você precisa e (ignorando pontos colineares)? (Os dígitos representam vértices e as bordas pares de dígitos em minha notação.)( 12 , 23 , 31 , 24 , 43 ) ( 12 , 23 , 31 , 14 , 24 , 34 )N(12,23,31,24,43)(12,23,31,14,24,34)
Szabolcs

Respostas:

4

Em Hartvigsen, D .: Reconhecendo os Diagramas de Voronoi com Programação Linear, são apresentados vários algoritmos baseados em programação linear para reconhecer as tesellações de Voronoi, e afirma que

[...] para cada de um diagrama de Voronoi, o conjunto de pontos em contidos em algum conjunto gerador é um singleton ou o interior de um poliedro.R i PRiRiP

Parece que o tópico da existência e singularidade da solução para o problema inverso de Voronoi também é desenvolvido em Winter, LG: O problema inverso do diagrama de Voronoi .

astrojuanlu
fonte
3N63N5D:R3NGNGNNND1:GNP(R3N6)D(RN)D1(g)gGN
Depois de entender suas preocupações e fazer algumas pesquisas, encontrei alguns recursos potencialmente úteis. Note, porém, que posso ler a versão em texto completo de nenhuma delas.
Astrojuanlu
Essas são referências interessantes. Minha biblioteca me fornecerá cópias.
Death Breath
Parece que esses árbitros são mais difíceis de obter do que o previsto.
Death Breath
De qualquer forma, obrigado pela recompensa, espero que sejam úteis quando você finalmente as receber.
Astrojuanlu