We study a variant of the geometric multicut problem, where we are given a set $\mathcal{P}$ of colored and pairwise interior-disjoint polygons in the plane. The objective is to compute a set of simple closed polygon boundaries (fences) that separate the polygons in such a way that any two polygons that are enclosed by the same fence have the same color, and the total number of links of all fences is minimized. We call this the minimum link fencing (MLF) problem and consider the natural case of bounded minimum link fencing (BMLF), where $\mathcal{P}$ contains a polygon $Q$ that is unbounded in all directions and can be seen as an outer polygon. We show that BMLF is NP-hard in general and that it is XP-time solvable when each fence contains at most two polygons and the number of segments per fence is the parameter. Finally, we present an $O(n \log n)$-time algorithm for the case that the convex hull of $\mathcal{P} \setminus \{Q\}$ does not intersect $Q$.
翻译：我们研究了几何多截问题的一种变体, 我们从中得到了一组彩色和对称内部分解多边形的彩色和对称内分解多边形。 目的是计算一组简单的封闭多边边框( 栅栏), 将多边形分隔开来, 使同一栅栏所包围的任何两个多边形都具有相同的颜色, 并且将所有栅栏的连接点总数最小化。 我们称之为最小链接栅栏问题, 并审议捆绑最小链接栅栏( BMLF) 的自然案例, 其中, $\ mathcal{ P} 包含一个多边方美元, 并且可以被视为外多边形。 我们表明, 普通的 BMLF是硬的, 当每个栅栏中的大多数是两个多边形, 并且每个栅栏的区段数是参数时, 它是XP- 时间可溶解的。 最后, 我们提出一个美元( n) 美元/ log n- 时间算法, 用于 $\\\ cal} 美元 内 QQset 。
相关内容
微信扫码咨询专知VIP会员