We are given a Graph, G(V, E), where V is the node set and E is the edge set consisting of ordered tuples (u, v). The graph is undirected, as such, if (u,v) is in E, then (v, u) is in E.

Alongside the graph, you are given an embedding of the graph in k-d space. Let the embedding function be P: V -> R^k.

For each node v in the graph, I want to compute its corresponding r such that: for all u, if Dist(P(v), P(u)) < r then (v, u) in E

In other terms, for every node v in the graph, I want to define a hyper-sphere with center v and radius r, such that all the points inside the sphere correspond to neighbors of v. Points lying outside the sphere can be a neighbor of v, but I want to maximize r until it reaches a roadblock or covers all neighbors. r should be the min{distance between v and its farthest neighbor, distance between v and its closest non-neighbor}.

One trivial way to do it is to compute the distance matrix and proceed from there. But computing that matrix requires O(n^2) time. Is it possible to do this in linear time or almost-linear time?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.