给定周长内封闭的最大点数 [英] maximum number of points enclosed in given perimeter

问题描述

给定一些点的坐标数组和固定周长的绳索，我如何计算这条绳索可以包含的最大点数？(我指的是除蛮力以外的算法)

例如：给定[[0,1],[0,0],[1,1],[1,0],[100,100]]和长度为4的绳索，则此绳索可以包含前4个点。

推荐答案

刚找到此链接：The minimum perimeter convex hull of a subset of a point set

投票最多的答案给出了寻找最小面积k-gon的来源，所以现在通过二进制搜索，复杂度可以是O(n^4*(Logn))

这篇关于给定周长内封闭的最大点数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！