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

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1993年 / 9卷 / 01期

关键词：

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