在最佳的区域K-坤给定一组点

根据我的理解这个问题的目的是寻找最大的K-坤区域，给定一组点D和k = < = n，n是固定值。

让d的凸包= C（d）

如果n = 3，我已经证明了这些三角形可以通过假设它的顶点是C（d）的子集来构建。所以很容易想出k = 3的解决方案：https://stackoverflow.com/a/1621913/4126652

但是，对于n> 3，我不知道如何做到这一点。

以下是我的尝试：

让| C（D）| = 1即，凸包是一个升边形，

如果n>利很肯定的是，K-坤具有最大面积将凸包本身，即C（d）

如果n <我很确定最大k-gon的顶点将是C（D）的一个子集，我不能证明它对于k> 3，并且我无法想出一个算法来解决，即使这是一个正确的假设。

任何人都可以帮助我，这是我的方法是否正确？你能帮我进一步吗？

2016-10-04 Vikash B

它是与k个边形最大面积 –

如果k <凸包中顶点的数目，该怎么办？ –

如果你看到我的措辞如何，欢迎你提出编辑建议 –

打破了我的头几个小时后，我想出了解决方案。

它是一个动态规划问题：

让DP [M] [O] [R]表示的最大面积的r-坤使得起始顶点为m和结束顶点为O（在采取顶点循环次序）。

然后递推关系将是：

DP [M] [O] [R] = MAX（DP [M] [N] [R-1] +区域（M，N，O））， {最大值在所有N：M <ñ<ö}

其中区域（M，N，O）是由顶点米所形成的三角形的面积，n和o

2016-10-04 19:58:16

回答