计算隶属超球面半径的线性时间算法

Question

给定一个图 G(V, E)，其中 V 是节点集，E 是由有序元组 (u, v) 组成的边集。该图是无向的，因此，如果 (u,v) 在 E 中，则 (v, u) 在 E 中。

除了图之外，还给出了图在 k-d 空间中的嵌入。令嵌入函数为 P: V -> R^k。

对于图中的每个节点 v，我想计算其相应的 r，以便： 对于所有 u，如果 Dist(P(v), P(u)) < r then (v, u) in E

换句话说，对于图中的每个节点 v，我想定义一个以 v 为中心、半径为 r 的超球体，使得球体内的所有点都对应于 v 的邻居。位于球体外的点可以是v 的邻居，但我想最大化 r 直到它到达障碍或覆盖所有邻居。 r 应该是最小值

{distance between v and its farthest neighbor, distance between v and its closest non-neighbor}

。

一种简单的方法是计算距离矩阵并从那里继续。但计算该矩阵需要 O(n^2) 时间。是否可以在线性时间或几乎线性时间内完成此操作？

Answer 1

“是否可以在线性时间或几乎线性时间内完成此操作？”

• 我不相信

  O(N)

  时间复杂度是解决这个多维图问题的选择。

• O(k * N ^ 2)

  时间复杂度是可能的。在具有无限维度的情况下，这甚至会导致

  O(N ^ 3)

  时间复杂度。

---

示例

import numpy as np
from collections import defaultdict


def get_min_max(nodes, edges, vects):
    n, res = len(nodes), defaultdict(int)
    SE = set(edges)
    SE.update((v, u) for u, v in edges)

    D = np.linalg.norm(vects[:, np.newaxis] - vects, axis=2)

    for i, v in enumerate(nodes):
        dists = D[i]
        neis, others = set(), set()
        for j, u in enumerate(nodes):
            if u == v:
                continue
            if (v, u) in SE:
                neis.add(dists[j])
            else:
                others.add(dists[j])

        far = max(neis) if neis else float('inf')
        near = min(others) if others else float('inf')

        res[v] = (max(far, near), min(far, near))

    return res


nodes = ('a', 'b', 'c', 'd', 'e', 'f', 'g')
edges = (('a', 'b'), ('a', 'e'), ('a', 'g'), ('b', 'c'), ('c', 'd'), ('c', 'g'), ('c', 'e'), ('d', 'e'),
         ('d', 'f'), ('f', 'd'), ('f', 'e'), ('f', 'c'), ('d', 'g'), ('g', 'b'), ('g', 'd'))
vects = np.array((
    (1, 0, 1),
    (1, 0, 1),
    (0, 1, 1),
    (0, 0, 1),
    (1, 1, 1),
    (1, 0, 1),
    (0, 1, 0),
))

print(get_min_max(nodes, edges, vects))

打印

defaultdict(<class 'int'>, {'a': (1.7320508075688772, 0.0), 'b': (1.7320508075688772, 0.0), 'c': (1.4142135623730951, 1.4142135623730951), 'd': (1.4142135623730951, 1.0), 'e': (1.4142135623730951, 1.0), 'f': (1.4142135623730951, 0.0), 'g': (1.7320508075688772, 1.4142135623730951)})