Given a geometric t-spanner graph G in Ed with n points and m edges, with edge lengths that lie within a polynomial (in n) factor of each other. Then, after O(m+n log n) preprocessing, we present an approximation scheme to answer (1+ε)-approximate shortest path queries in O(1) time. The data structure uses O(n log n) space.
展开▼
机译：给定E d 中具有 n 个点的几何 t -跨度图 G m 条边，边长在彼此的多项式（ n ）因数之内。然后，在 O （ m + n log n ）预处理之后，我们提出一种近似方案来回答（1 +ε）- O （1）时间中的最短路径查询。数据结构使用 O （ n log n ）空间。
展开▼
