Optimal Binary Space Partitions in the Plane
Optimal Binary Space Partitions in the Plane
复制标题
DOI：
10.1007/978-3-642-14031-0_25
复制
发表时间：
2010-07
期刊：
影响因子：
--
通讯作者：
M. D. Berg;Amirali Khosravi
中科院分区：
文献类型：
--
作者：
M. D. Berg;Amirali Khosravi
对于平面中不相交线段的集合S，最优的bsp是产生最少切割次数的bsp。我们研究了三类bsp的最优bsp，它们在递归分区过程中分区一组片段时可以使用的分割线不同：freebsp可以使用任何分割线，restricteddbsp只能使用通过片段端点对的分割线，auto-partitioncan只能使用包含片段的分割线。我们得到了以下两个结果：它是np-难决定是否一个给定的段集允许一个自动划分，不作任何削减。一个最佳的restricteddbsp最多2倍，为同一组段的最佳freebsp削减。
An optimalbspfor a setSof disjoint line segments in the plane is abspforSthat produces the minimum number of cuts. We study optimalbspsfor three classes ofbsps, which differ in the splitting lines that can be used when partitioning a set of fragments in the recursive partitioning process:freebspscan use any splitting line,restrictedbspscan only use splitting lines through pairs of fragment endpoints, andauto-partitionscan only use splitting lines containing a fragment. We obtain the two following results:It isnp-hard to decide whether a given set of segments admits an auto-partition that does not make any cuts.An optimal restrictedbspmakes at most 2 times as many cuts as an optimal freebspfor the same set of segments.