Complexidade da localização em redes sem fio

12

Deixe pontos distintos sentar em R 2 . Dizemos pontos i e j são vizinhos se | i - j | < 31...nR2ij , significando que cada ponto é vizinho de pontos com índices dentro de 2 , contornando.|ij|<3(modn2)2

O problema é:

Para cada par de vizinhos, são dadas suas distâncias aos pares (e sabemos qual distância corresponde a quais pontos), e queremos reconstruir as distâncias aos pares de todos os pontos. Minhas perguntas são: qual é a complexidade desse problema de localização?

Não conheço um algoritmo de tempo polinomial.

Isso é motivado por problemas na localização em redes de sensores , onde os agentes, colocados ad-hoc, podem se comunicar sem fio com seus vizinhos lexicográficos, e queremos reconstruir suas posições.

Não sei muito sobre problemas de geometria / localização, portanto isso pode ser fácil ou conhecido. O problema mais próximo que conheço é o problema do Turnpike , apontado recentemente neste fórum por @Suresh Venkat.

Lev Reyzin
fonte
bem definido? se dois pontos puderem pousar no mesmo ponto em R ^ 2, você poderá fazer dobradiças.
RJK
desculpe consertar ...
Lev Reyzin
1
Lev, parece que o tex agora está ativado. você pode tentar editar sua postagem para usar o látex e ver se funciona?
Suresh Venkat
você não esclareceu se é dada uma distância d Eu sei qual par (i, j) o fez. a diferença é crucial
Suresh Venkat
@suresh - Esclarei sua pergunta - sabemos as distâncias correspondentes. também o suporte ao tex é ótimo! @Jukka - obrigado, vou verificar o seu link.
Lev Reyzin

Respostas:

4

(Eu não tenho uma resposta real, mas isso foi muito longo para um comentário, portanto, poste aqui de qualquer maneira ...)

Eu suspeito que o problema é NP-difícil, por redução do problema da soma do subconjunto. Uma ideia de prova:

Redução: se o ésimo elemento na instância da soma do subconjunto for x i , a distância entre os nós 2 i - 1 e 2 i é s , distância entre 2 i - 1 e 2 i + 1 é x i , distância entre 2 i e 2 i + 2 também é x i , e a distância entre 2 i e 2 i + 1 éixi2i12is2i12i+1xi2i2i+2xi2i2i+1 .s2+xi2

2i12ii2i+22i2in=2k22k112k12

s2kxi

Jukka Suomela
fonte
ideia interessante - obrigado. uma pergunta rápida de esclarecimento - o que permite assumir que todas as arestas de 1 vizinho são verticais?
Lev Reyzin
1
Só estou assumindo que as arestas 1-2, 3-4, ... são verticais. É claro que você pode escolher a orientação da aresta 1-2 arbitrariamente e definir que ela é "vertical". Depois, existem apenas duas configurações possíveis para a borda 3-4: ela é vertical ou você "virou" (espelhado) ao longo da borda 2-3. Gostaríamos de evitar a segunda possibilidade que complica a prova; veja a parte "até agora tudo bem ..." para uma possível idéia de como lidar com isso.
Jukka Suomela
Entendo - boa idéia
Lev Reyzin
Thm 4.1 (pág. 50) de cs.yale.edu/homes/dkg6/papers/thesis.pdf esta tese diz que o quadrado de qualquer gráfico com 2 conexões tem uma localização única. Como você apresentou uma localização global que é encontrada ao resolver a soma de subconjuntos, sabemos que não há mais respostas (e não precisamos nos preocupar com desvios na diagonal). Eu acho que isso termina a prova!
Lev Reyzin
6

Na verdade, é NP-difícil. Veja o documento a seguir para referências.

Sriram V. Pemmaraju, Imran A. Pirwani: Realização virtual de boa qualidade de gráficos de esferas unitárias. SEC 2007: 311-322

Imran Rauf
fonte
1
As referências realmente cobrem o caso especial mencionado no OP? Ou seja, sua topologia gráfica é o quadrado de um ciclo?
Jukka Suomela
1
Você está tão certo. Abrange apenas os casamentos no R ^ d.
Imran Rauf
Boa referência embora - obrigado
Lev Reyzin