给定一个由 n 个顶点组成的简单多边形 P 和 Set S Of k 个点，确定每个多边形顶点是否都被 S 中的某个点覆盖
Given a simple polygon P, consisting of n vertices, and Set S Of k points, determine if each of the polygon vertices are covered by some point from S
给定一个由 n 个顶点组成的简单多边形 P，以及包含 k 个点的集合 S，确定每个多边形顶点是否都被 S 中的某个点覆盖。
我最好的解决方案是检查每个 P 顶点是否在 S 中存在这样的点 - 总复杂度为 O(n*k)。我相信应该有一个更有效的解决方案。有什么提示吗？
P是不是多边形似乎无关紧要。所以一般化的问题就变成了：给定 2 组点 A（有 a 点）和 B（有 b 点），找出 A 是否是 B 的子集？
简单的解决方案是 O(a * b)，但您也可以通过一些预处理得到 O(a + b)。
将B的所有点放入以x-coordinate为键和以y-coordinates为值的散列集(Map<Number,Set<Number>>)中的散列映射中。这使您可以在 O(1) 中查询点 (x, y) 是否在 B 中：map.containsKey(x) && map.get(x).contains(y).
遍历 A 的所有点并使用上面创建的数据结构检查该点是否在 B 中。
第 1 步是 O(b)，第 2 步是 O(a)，得到 O(a + b)。
给定一个由 n 个顶点组成的简单多边形 P，以及包含 k 个点的集合 S，确定每个多边形顶点是否都被 S 中的某个点覆盖。
我最好的解决方案是检查每个 P 顶点是否在 S 中存在这样的点 - 总复杂度为 O(n*k)。我相信应该有一个更有效的解决方案。有什么提示吗？
P是不是多边形似乎无关紧要。所以一般化的问题就变成了：给定 2 组点 A（有 a 点）和 B（有 b 点），找出 A 是否是 B 的子集？
简单的解决方案是 O(a * b)，但您也可以通过一些预处理得到 O(a + b)。
将B的所有点放入以x-coordinate为键和以y-coordinates为值的散列集(
Map<Number,Set<Number>>)中的散列映射中。这使您可以在 O(1) 中查询点 (x, y) 是否在 B 中：map.containsKey(x) && map.get(x).contains(y).遍历 A 的所有点并使用上面创建的数据结构检查该点是否在 B 中。
第 1 步是 O(b)，第 2 步是 O(a)，得到 O(a + b)。