algorithm - 最大空圆 voronoi 图的参考

Question

我需要一些参考来理解我的想法：

给定最大的空圈问题，我想确定在哪里放置新商场

我的问题：如果我有一张被海一分为二的地图，我的 voronoi 图会通过这些点而不考虑地理限制（即，如果有人住在地图的左侧，那个人就不想越过海去商场）

是否有可能或参考来处理这个问题？

顺便说一句，我之前读过《财富》的算法

Answer 1

在我看来，您想限制最大空圆（LEC）的中心 C 的位置。

摘要：TOUSSAINT, Godfried T. 计算具有位置限制的最大空圆。International Journal of Computer & Information Sciences , 1983, 12.5: 347-358, 说：

特别是，如果将 C 的中心约束在任意凸 n 边形中，仍然可以获得 O(n log n) 算法。

还有：CHEW, L. Paul；德里斯代尔，苏格兰。查找具有位置限制的最大空圆圈。1986.说：

我们还改进了 Toussaint 给出的一种算法，用于在中心被限制在任意简单多边形内时计算 LEC。