论文标题
使用凸形多边形的整数编程公式
An integer programming formulation using convex polygons for the convex partition problem
论文作者
论文摘要
平面中的点集P的凸线分区是P的平面分区，该凸的凸面的平面分区带有空凸多边形或极端属于P的内部面部。此外，不允许多边形在其内部包含P点。问题是根据最小内部面部数量找到凸形分区。该问题已被证明是NP-HARD，最近在CG：Shop Challenge 2020中使用了。我们提出了一种新的整数线性编程（IP）配方，该配方对现有挑战进行了大大改进。它依赖于面孔的代表，而不是段和点。许多几何特性用于增强它。 100点的数据集很容易解决到最优性，并且模型提供的下限最多可以计算出300点。
A convex partition of a point set P in the plane is a planar partition of the convex hull of P with empty convex polygons or internal faces whose extreme points belong to P. In a convex partition, the union of the internal faces give the convex hull of P and the interiors of the polygons are pairwise disjoint. Moreover, no polygon is allowed to contain a point of P in its interior. The problem is to find a convex partition based on the minimum number of internal faces. The problem has been shown to be NP-Hard and was recently used in the CG:SHOP Challenge 2020. We propose a new integer linear programming (IP) formulation that considerably improves over the existing one. It relies on the representation of faces as opposed to segments and points. A number of geometric properties are used to strengthen it. Data sets of 100 points are easily solved to optimality and the lower bounds provided by the model can be computed up to 300 points.
