algorithm - 使用 d3 voronoi 查找最近邻居的运行时间

Question

d3.voronoi.find 方法的运行时间复杂度是多少？

在这里，https://visionscarto.net/the-state-of-d3-voronoi ，据说它的原始速度是 O(sqrt(n))，但有什么证据呢？

还有，有没有什么方法可以只用O(logn)时间计算出的voronoi图来寻找最近邻？

Answer 1

如您所见，following code是 find 函数，它被讨论过:

find: function(x, y, radius) {
    var that = this, i0, i1 = that._found || 0, n = that.cells.length, cell;

    // Use the previously-found cell, or start with an arbitrary one.
    while (!(cell = that.cells[i1])) if (++i1 >= n) return null;
    var dx = x - cell.site[0], dy = y - cell.site[1], d2 = dx * dx + dy * dy;

    // Traverse the half-edges to find a closer cell, if any.
    do {
      cell = that.cells[i0 = i1], i1 = null;
      cell.halfedges.forEach(function(e) {
        var edge = that.edges[e], v = edge.left;
        if ((v === cell.site || !v) && !(v = edge.right)) return;
        var vx = x - v[0], vy = y - v[1], v2 = vx * vx + vy * vy;
        if (v2 < d2) d2 = v2, i1 = v.index;
      });
    } while (i1 !== null);

    that._found = i0;

    return radius == null || d2 <= radius * radius ? cell.site : null;
}

根据指定的半径搜索数据点。无论如何，如您所见，它遍历所有半边(因此，在最坏的情况下它可能是 O(n))。

无论如何，通过良好的数据结构可以找到 log(n) 中的最近邻居。可以看到this answer了解更多。