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

Question

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

我想知道是否有任何有效的算法来解决这个问题？您能否提出任何与此问题相关的关键字/论文/任何内容？

编辑:矩形始终由角落中的4个点定义.我添加了一张图片用于说明.上图中的路径由两条红线决定

Answer 1

这是最宽的空走廊问题.Houle和Maciel 在1988年的一份技术报告中给出了一个O(n ²)时间O(n)空间算法,该报告名为"通过一组点找到最宽的空走廊",这似乎无法在线获得.幸运的是,Janardan和Preparata在他们的论文最广泛走廊问题的第4节中描述了这种算法.