时间戳

首页 > 解决方案 > 在网格上找到与给定集合的最大曼哈顿距离的点集

algorithm - 在网格上找到与给定集合的最大曼哈顿距离的点集

问题描述

给定一个边为 N 的正方形网格。同时给定网格上的一组输入点。需要在网格上找到另一组点（可以是多个），它们与给定输入点的曼哈顿距离最大。

例如N = 4，输入[p1:{0, 0}, p2:{3, 3}]和输出的距离应该[{0, 3}, {1, 2}, {2, 1}, {3, 0}]等于 3。

      0   1   2   3
    ┌───┬───┬───┬───┐
  0 │p1 │   │   │ x │
    ├───┼───┼───┼───┤
  1 │   │   │ x │   │
    ├───┼───┼───┼───┤
  2 │   │ x │   │   │
    ├───┼───┼───┼───┤
  3 │ x │   │   │p2 │
    └───┴───┴───┴───┘

我的第一次尝试是简单的蛮力迭代——为网格中的每个点计算曼哈顿到每个输入点的距离，取最小值，最后从这些最小值中取最大值。这当然有效，但在大 N 和输入上很慢。

在我的第二次尝试中，我首先构建了一个 kd-tree。接下来迭代几乎与以前相同，不同之处在于现在我不计算到每个输入点的距离，而是到最近的一个（或多个）。这有点帮助，但仍然有人告诉我有更好的算法。

标签： algorithmdata-structures

解决方案

您应该使用广度优先搜索，从所有给定点开始，同时找到每个单元格与其最近点的距离。这需要线性时间并且很容易编码。

然后找到最高距离（或者记住它，因为它将是你写的最后一个），并返回具有该距离的所有单元格。

如果你的点不是太稀疏，那会很好用。如果它们相隔很远，那么您将需要一种算法，它会随着点数而不是网格的大小而增长。这将基于计算曼哈顿距离 Voronoi 图，因为您要返回的所有点都在其上。

推荐阅读