MINIMUM DISSECTION OF A RECTILINEAR POLYGON WITH ARBITRARY HOLES INTO RECTANGLES

被引:25
作者
SOLTAN, V
GORPINEVICH, A
机构
[1] Institute of Mathematics, Moldavian Academy of Sciences, Kishinev, 277028
关键词
D O I
10.1007/BF02189307
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
In this paper, the problem of dissecting a plane rectilinear polygon with arbitrary (possibly, degenerate) holes into a minimum number of rectangles is shown to be solvable in O(n3/2 log n) time. This fact disproves a famous assertion about the NP-hardness of the minimum rectangular dissection problem for rectilinear polygons with point holes.
引用
收藏
页码:57 / 79
页数:23
相关论文
共 11 条
[11]  
SOLTAN V, 1988, GEOMETRIE ANWENDUNGE, P111