algorithm - 通过一组点找到最宽的空直线路径

Question

我正在创建一个简单的游戏，并在为我的游戏设计 AI 时遇到了这个问题: 给定笛卡尔坐标矩形内的一组 N 个点，我需要找到通过该矩形的最宽直线路径。路径必须为空(即不包含任何点)。

请问有没有什么高效的算法可以解决这个问题？你能建议任何与这个问题相关的关键词/论文/任何东西吗？

编辑:矩形总是由其角上的 4 个点定义。我添加了一个图像来说明。上图中的路径是由两条红线决定的

Answer 1

这是最宽的空走廊问题。 Houle 和 Maciel 在 1988 年题为“通过一组点找到最宽的空走廊”的技术报告中给出了 O(n²)-时间、O(n)-空间算法，这似乎与在线提供。幸运的是，Janardan 和 Preparata 在他们论文的第 4 节中描述了这个算法 Widest-corridor problems , 这是可用的。