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

共 11 条

[1] MINIMAL RECTANGULAR PARTITIONS OF DIGITIZED BLOBS [J].

FERRARI, L ;

SANKAR, PV ;

SKLANSKY, J .

COMPUTER VISION GRAPHICS AND IMAGE PROCESSING, 1984, 28 (01) :58-71

[2]

GORPINEVICH AN, 1908, B ACAD SCI MOLD PTMS, P19

[3] EFFICIENT ALGORITHMS FOR GEOMETRIC GRAPH SEARCH PROBLEMS [J].

IMAI, H ;

ASANO, T .

SIAM JOURNAL ON COMPUTING, 1986, 15 (02) :478-494

[4]

KORNIENKO NM, 1978, IZV AKAD NAUK BS PMS, P25

[5]

LINGAS A, 1982, LECT NOTES COMPUT SC, V140, P369

[6] AN O(N LOG N) MANHATTAN PATH ALGORITHM [J].

LIPSKI, W .

INFORMATION PROCESSING LETTERS, 1984, 19 (02) :99-102

[7] FINDING A MANHATTAN PATH AND RELATED PROBLEMS [J].

LIPSKI, W .

NETWORKS, 1983, 13 (03) :399-409

[8]

LIPSKI W, 1979, FUND INFORM, V2, P245

[9]

RUBTSOV VP, 1976, ELECTRONNAYA TEHNICA, V3, P54

[10]

SOLTAN V, 1985, REPUBLICAN SEMINAR D, P107

← 1 2 →