Detectando coplanaridade por distâncias dadas em pares

Considere um gráfico ponderado não direcionado , em que modo que os pontos sejam 3D, e o peso de uma aresta seja igual à distância (euclidiana) entre seus pontos finais. Observe que não recebemos as coordenadas dos pontos em V. Podemos nem mesmo ter todas as distâncias aos pares, portanto o gráfico não precisa estar completo e pode ser esparso.$G = (V,E)$$V \subset \mathbb{R}^3$

Suponha que recebemos e avisemos que existem planos de modo que todos os vértices pertencem a pelo menos um desses planos. Queremos encontrar tais aviões, com uma restrição adicional:$k$$k$$k$

Para determinar se 4 pontos são coplanares, dadas apenas suas distâncias aos pares, o método mais direto é usar o determinante de Cayley-Menger . Para o nosso problema, isso exigiria que o gráfico fosse bastante denso, pois precisaríamos conhecer a maioria das distâncias aos pares para aplicar Cayley-Menger. A restrição é encontrar aviões sem usar o determinante de Cayley-Menger.$k$

Se isso for impossível, podemos obter uma prova de que isso é impossível? Em outras palavras, podemos provar que, para qualquer gráfico e dado , se tivermos informações suficientes para encontrar planos para de alguma maneira, teremos informações suficientes para usar Cayley-Menger para encontrar planos?$G$$k$$k$$G$$k$

Eu acho que se o gráfico de entrada estiver conectado em 3 e você assumir alguma origem e orientação arbitrárias, poderá recriar os pontos originais. Especialmente se você encontrar K_4 para propagar o processo de triangulação.

Uma vez que temos os pontos, estratégias gananciosas se tornam disponíveis. Eles podem não ser ótimos, mas talvez sejam suficientes para seus propósitos.

Eu perguntei sobre a recuperação da incorporação como uma pergunta separada.

Random Greedy

Até que tenhamos menos de três pontos não desqualificados, escolha arbitrariamente três deles, produza o avião passando por eles e marque todos os pontos do avião como desqualificados.

Pegue os pontos restantes não desqualificados (se houver), emparelhe-os com alguns pontos desqualificados arbitrários e produza o avião passando por eles.

Os aviões que produzimos cobriram todos os pontos. O número de planos que produzimos é no máximo , e cada um requer a varredura pelos pontos restantes, portanto, esse algoritmo leva tempo (mais rápido que calcular um determinante).$\frac{n}{3}$$O(n^2)$

Se o número de aviões , então temos chances razoavelmente boas de atingir um dos aviões grandes. Não sei ao certo qual é o tempo de execução esperado , mas gostaria de adivinhar em . (Isso se baseia no problema do coletor de cupons, implicando que precisamos de hits para coletar aviões, e que as chances de um hit são portanto o tempo esperado entre os hits é ).$k \ll n$$O(n \, k^3 \log k)$$\approx k \log k$$k$$\approx (1/k)^2$$\approx k^2$

Ganancioso Priorizado

Outra coisa que podemos fazer, se conseguirmos resolver os pontos, é iterar todos os trigêmeos e contar quantos pontos existem nesse plano. Em seguida, produzimos repetidamente o plano que cobre o maior número de pontos, até que nenhum ponto seja deixado.

Se não considerarmos pontos desqualificados ao escolher o próximo plano, isso levará tempo em que é o número de planos que retornamos. Se voltarmos a priorizar, acho que ainda pode ser feito em (o número de pontos desqualificados em outros planos pode mudar apenas em 2, portanto, é possível reequilibrar de alguma maneira inteligente )$O(n^3 \log t)$$t$$O(n^3 \log t)$

Essa abordagem deve se sair melhor, mas, novamente, não acho que seja garantido que . Provavelmente, podemos organizar os pontos para que pegar o avião que cobre a maioria deles nos leve ao caminho errado.$t=k$

O RANSAC seria um método candidato para encontrar aviões que cobrissem uma grande fração dos pontos.

Suponha que uma grande fração dos pontos passe por algum plano , digamos, deles. Veja como podemos encontrá-lo:$P$$n/10$

Então, vamos escolher 4 pontos aleatoriamente a partir do ; chame esses pontos de . Suponha que conheçamos as distâncias entre todos esses pares (eles formam um 4-clique, ). Em seguida, podemos usar o determinante Cayley-Menger para ver se eles são co-planares. Suponha que eles sejam co-planares. Então, podemos tentar testar um ao outro o ponto e ver se podemos dizer se é co-plano com o plano formado por . Só poderemos testar isso quando o ponto adicional formar um 4-clique junto com alguns outros pontos conhecidos no plano. No final, se encontrarmos um número significativo de pontos que estão no plano formado por$n$$q,r,s,t$$K_4$$x$$q,r,s,t$$u$$q,r,s,t$, mantemos este plano. Continue fazendo isso por, digamos, 1000 opções aleatórias de .$q,r,s,t$

Quão bem isso vai funcionar? Bem, suponha que modelemos o gráfico como um gráfico aleatório em que cada aresta possível apareça com probabilidade (então esperamos arestas em média). Então a probabilidade de que um conjunto de 4 pontos escolhido aleatoriamente forme um 4-clique no gráfico é . Portanto, se experimentar, pelo menos, escolhas de , espera-se encontrar, pelo menos, uma, onde eles revelam o plano . Além disso, a probabilidade de que um ponto adicional forme um 4-clique com pelo menos três de é , portanto, quando encontramos quatro pontos no plano$p$$pn(n-1)/2$$p^6$$10^4/p^6$$q,r,s,t$$P$$u$$p,q,r$$p^3$$q,r,s,t$$P$, Espera-se encontrar, pelo menos, dos pontos no plano . (Na verdade, provavelmente encontraremos muito mais do que isso. Quando tivermos esses pontos, agora a probabilidade de um ponto adicional formar um 4-clique com pelo menos três deles é , que é significativamente maior que ) Em outras palavras, uma vez que encontramos pontos no plano , é provável que manteremos esse plano.$p^3 n/10$$P$$p^3 n/10$$v$$1-(1-p^3)^{p^3 n/10} \approx 1-\exp\{-p^6 n/10\}$$p^3$$q,r,s,t$$P$

Portanto, desde que você experimente 4 combinações de pontos suficientes e o gráfico seja denso o suficiente, esse procedimento provavelmente detectará todos os planos que cobrem uma grande fração de pontos.

Infelizmente, a resposta é que este é um problema do NP-Complete. Usando apenas 4 planos de pontos, é possível codificar problemas de satisfação para saber se existe ou não um conjunto de pontos que gera um conjunto esparso de distâncias.

Isso significa que você pode criar problemas onde determinar se um quinto plano é necessário ou não requer a solução de problemas 3-SAT. Você pode combinar dois desses problemas, em que exatamente um requer o quinto plano, para manter constante o número de planos e forçar o algoritmo a resolver problemas de 3-SAT, mesmo que ele saiba antecedência.$k$

Portanto, o problema não tem solução de tempo polinomial para o pior caso, a menos que P = NP.

Estou tentando uma resposta, mesmo que a pergunta possa ser pouco clara. metade diz que os pontos são dados, a outra metade diz que distâncias aos pares são dadas. vou assumir que são dadas coordenadas de ponto para esta resposta. existe uma conexão estreita entre o determinante da computação e a classificação da matriz. existe uma generalização da seguinte maneira. criar a matriz de vetores 3d, eles podem ser vetores de coluna ou linha. calcular a classificação . se for 2, os pontos são coplanares. as distâncias aos pares podem ser calculadas a partir das coordenadas e não é necessário calcular / determinar a classificação da matriz.