使用黑盒算法查找具有最小面积的多边形,以获取最大面积

问题描述 投票:1回答:1

让S为平面中的一组点。在这组点上,我们想要构造简单的多边形。多边形的拐角应该恰好是来自S的点,并且多边形的边缘不应相交(或仅在公共拐角处)。假设我们有一个算法,可以在T(n)的时间内返回具有n个节点的任何点集上具有最大面积的多边形。对于给定的S,我们现在想找到面积最小的多边形。

问题是如何使用这种黑盒算法为我们提供面积最大的多边形,以便找到面积最小的多边形。我被困住了,不知道如何继续,因为我不了解如何使用该黑盒算法。任何提示将不胜感激。

algorithm geometry polygon computational-geometry
1个回答
0
投票

构造给定点的多边形边界框,并复制此框的一个角以及从该角“可见”的集合中的一个点。

最大化算法应生成具有最小孔的多边形。

© www.soinside.com 2019 - 2024. All rights reserved.