论文标题
计算最小的凸相交多边形
Computing Smallest Convex Intersecting Polygons
论文作者
论文摘要
如果C相交O中的每个对象，则多边形C是平面对象的集合的多边形，其中多边形包括其内部。我们研究了为给定的对象集合O的最小值相交多边形和最小面积凸的最小值相交多边形的问题。对于这两个问题，我们为O是一组可能与总复杂性n平面相交的凸多边形的情况提供了一个FPTA。 此外，我们为最小值相交多边形的情况提供了一种精确的多项式时间算法，其中O是一组N可能在平面中相交的n段。到目前为止，多项式时间精确算法仅因最小周长与线或不连接段的多边形相交而闻名。
A polygon C is an intersecting polygon for a set O of objects in the plane if C intersects each object in O, where the polygon includes its interior. We study the problem of computing the minimum-perimeter intersecting polygon and the minimum-area convex intersecting polygon for a given set O of objects. We present an FPTAS for both problems for the case where O is a set of possibly intersecting convex polygons in the plane of total complexity n. Furthermore, we present an exact polynomial-time algorithm for the minimum-perimeter intersecting polygon for the case where O is a set of n possibly intersecting segments in the plane. So far, polynomial-time exact algorithms were only known for the minimum perimeter intersecting polygon of lines or of disjoint segments.
