0

给定一个 DCEL，我如何找到最近的一对站点？

假设给定的 DCEL 用于 Voronoi 图，我如何找到最近的一对站点？时间复杂度是多少？

4

1 回答 1

1

最简单的方法是遍历所有边，找到它们的相邻面，计算 Voronoi 中心之间的距离，然后返回最小的对。如果您的 DCEL 实现无法直接在边上进行迭代，则可以使用任何图遍历算法（深度优先、广度优先等）进行迭代。

在任何情况下，时间复杂度都与输入数据结构的大小成正比。

于 2012-09-24T19:56:06.093 回答