Fast, precise and dynamic distance queries

Yair Bartal, Lee-Ad Gottlieb, Tsvi Kopelowitz +2

We present an approximate distance oracle for a point set S with n points and doubling dimension λ. For every ε>0, the oracle supports (1+ε)-approximate distance queries in (univer…