Complexidade de calcular os caminhos mais curtos do avião com obstáculos poligonais

22

Suponha que recebamos vários polígonos simples disjuntos no plano e dois pontos e fora de cada polígono. O problema do caminho mais curto euclidiano é calcular o caminho mais curto euclidiano de a que não cruza o interior de nenhum polígono. Para concretude, vamos assumir que as coordenadas de e , e as coordenadas de todos os vértices poligonais, são números inteiros.t s t s tststst

Esse problema pode ser resolvido em tempo polinomial?

A maioria dos geômetros computacionais diria imediatamente que sim, é claro: John Hershberger e Subhash Suri descreveram um algoritmo que calcula os caminhos mais curtos euclidianos no tempo , e esse tempo limite é ideal no modelo de árvore computacional algébrica. Infelizmente, o algoritmo de Hershberger e Suri (e quase todos os algoritmos relacionados antes e depois) parece exigir aritmética real exata no forte sentido a seguir.O(nlogn)

Chame um caminho poligonal válido se todos os seus vértices internos forem vértices de obstáculos; todo caminho mais curto euclidiano é válido. O comprimento de qualquer caminho válido é a soma das raízes quadradas dos números inteiros. Assim, comparar os comprimentos de dois caminhos válidos requer a comparação de duas somas de raízes quadradas, o que não sabemos fazer em tempo polinomial .

Além disso, parece completamente plausível que uma instância arbitrária do problema da soma das raízes quadradas possa ser reduzida a um problema euclidiano equivalente de caminho mais curto.

Então: existe um algoritmo de tempo polinomial para calcular os caminhos mais curtos euclidianos? Ou é o problema NP-difícil? Ou a soma das raízes quadradas é difícil ? Ou alguma outra coisa?

Algumas notas:

  • Os caminhos mais curtos dentro (ou fora) de um polígono podem ser calculados em tempo sem problemas numéricos estranhos usando o algoritmo de funil padrão, pelo menos se for dada uma triangulação do polígono.O(n)

  • Na prática, a aritmética de ponto flutuante é suficiente para calcular os caminhos mais curtos até a precisão do ponto flutuante. Estou interessado apenas na complexidade do problema exato .

  • John Canny e John Reif provaram que o problema correspondente no espaço 3 é NP-difícil (moralmente porque pode haver um número exponencial de caminhos mais curtos). Joonsoo Choi, Jürgen Sellen e Chee-Keng Yap descreveram um esquema de aproximação de tempo polinomial.

  • Simon Kahan e Jack Snoeyink consideraram questões semelhantes para o problema relacionado de caminhos de link mínimo em um polígono simples.

Jeffε
fonte
4
seria bom se houvesse uma lista de problemas difíceis de soma de raízes quadradas.
Suresh Venkat
4
Isso soa como uma pergunta perfeita para a história. Por que você não pergunta?
Peter Shor

Respostas:

4

Talvez eu sinta falta de alguma coisa, mas se considerarmos o caso "fácil", onde todos os obstáculos são pontos, temos o problema de calcular o caminho mais curto entre dois vértices em um gráfico planar, que, se não estiver errado, é conhecido. como somas-de-raízes-quadradas-duras.

PS. Queria adicionar um comentário e não uma resposta, mas não consigo encontrar como. Me desculpe por isso. Os administradores podem me ajudar com isso.

Elias
fonte
Você precisa de 50 reputação para postar um comentário em stackexchange. Mais detalhes aqui: cstheory.stackexchange.com/privileges/comment . Como você está fornecendo algumas informações, acho que não há problema em publicá-las como resposta.
chazisop
1
No caso "fácil", onde os obstáculos são pontos, o caminho mais curto euclidiano (ou mais formalmente, o caminho do infinito) é sempre um segmento de linha reta, e computá-lo é trivial. Mas mesmo para os caminhos mais curtos em gráficos planares com comprimentos de arestas euclidianas, você tem uma referência para a dureza da soma das raízes? (Não é difícil ver uma redução para os gráficos de quatro dimensões, porque todo inteiro é a soma de, no máximo, quatro quadrados perfeitos.)
Jeffε
3
Assim, no plano, isso reduzirá à soma das raízes quadradas de números inteiros, que são produtos de quadrados e primos da forma ? Acho que nunca vi nenhuma referência a esse problema antes, mas agora é óbvio que é bastante relevante para a geometria computacional. Talvez você deva colocar essa observação em sua pergunta. 4k+1
Peter Shor
Você está certo. O caso "fácil" é bastante trivial.
Elias