论文标题
凸出问题和新颖解决方案的自然扩展
A natural extension to the convex hull problem and a novel solution
论文作者
论文摘要
我们通过引入多重性来研究对众所周知的凸面问题的自然扩展：如果我们获得了一组凸多边形，并且我们可以将集合分为多个组成部分并将每个单个组件的凸面分开，那么convex hulls的最小总和的最小总和是多少？我们展示了为什么这个问题很有趣，然后引入了一种带有运行时立方体的新型算法。如果输入多边形是不相交的，我们显示了实现运行时的优化，在大多数情况下，在对数因子内，多边形在多边形总数中是立方体。
We study a natural extension to the well-known convex hull problem by introducing multiplicity: if we are given a set of convex polygons, and we are allowed to partition the set into multiple components and take the convex hull of each individual component, what is the minimum total sum of the perimeters of the convex hulls? We show why this problem is intriguing, and then introduce a novel algorithm with a run-time cubic in the total number of vertices. In the case that the input polygons are disjoint, we show an optimization that achieves a run-time that, in most cases, is cubic in the total number of polygons, within a logarithmic factor.
