Oráculo de Distância Aproximada para Spanners Geométricos Tolerantes a Falhas

Neste artigo, apresentamos oráculos de distância aproximada e caminho mais curto para spanners Euclidianos tolerantes a falhas, motivados pelo problema de roteamento em redes viárias do mundo real. Um spanner Euclidiano tolerante a falhas para um conjunto de pontos no espaço Euclidiano é um grafo em que, apesar da exclusão de um pequeno número de pontos, a distância entre quaisquer dois pontos no grafo danificado é uma aproximação de sua distância Euclidiana. Dado um spanner Euclidiano tolerante a falhas e um pequeno fator de aproximação, nossa estrutura de dados nos permite calcular uma distância aproximada entre dois pontos no spanner danificado em tempo constante quando uma consulta envolve quaisquer dois pontos e um pequeno conjunto de pontos falhos. Além disso, ao incorporar estruturas de dados adicionais, podemos retornar o próprio caminho em um tempo quase linear em relação ao comprimento do caminho retornado. Ambas as estruturas de dados requerem espaço quase linear.