The number of guillotine partitions in d dimensions

被引：11

作者：

Ackerman, E

Barequet, G ^{[1
]}

Pinter, RY

Romik, D

机构：

[1] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel

[2] Weizmann Inst Sci, Dept Math, IL-76100 Rehovot, Israel

来源：

INFORMATION PROCESSING LETTERS | 2006年 / 98卷 / 04期

关键词：

combinatorial problems; guillotine partitions; binary space partitions;

D O I：

10.1016/j.ipl.2006.01.011

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Guillotine partitions play an important role in many research areas and application domains, e.g., computational geometry, computer graphics, integrated circuit layout, and solid modeling, to mention just a few. In this paper we present an exact summation formula for the number of structurally-different guillotine partitions in d dimensions by n hyperplanes, and then show that it is Theta((2d - 1 + 2 root d-(d- 1))(n)/n(3)/(2)), root (c) 2006 Elsevier B.V. All rights reserved.

引用

页码：162 / 167

页数：6

共 13 条

[1]

[Anonymous], 1995, HDB COMBINATORICS

[2]

BALLIEUX C, 1993, INFSRC9325 UTR U NET

[3]

Chin N., 1989, Computer Graphics, V23, P99, DOI 10.1145/74334.74343

[4]

DU DZ, 1986, MSR021886 U CAL BERK

[5]

Fuchs H., 1980, Computer Graphics, V14, P124, DOI 10.1145/965105.807481

[6] IMPROVED BOUNDS FOR RECTANGULAR AND GUILLOTINE PARTITIONS [J].

GONZALEZ, T ;

ZHENG, SQ .

JOURNAL OF SYMBOLIC COMPUTATION, 1989, 7 (06) :591-610

[7] ON OPTIMAL GUILLOTINE PARTITIONS APPROXIMATING OPTIMAL D-BOX PARTITIONS [J].

GONZALEZ, TF ;

RAZZAZI, M ;

SHING, MT ;

ZHENG, SQ .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1994, 4 (01) :1-11

[8]

LENGAUER T, 1990, COMBINATORIAL ALGORT

[9] Guillotine subdivisions approximate polygonal subdivisions:: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems [J].

Mitchell, JSB .

SIAM JOURNAL ON COMPUTING, 1999, 28 (04) :1298-1309

[10]

Odlyzko A.M., 1995, Handbook of Combinatorics, V2, P1063

← 1 2 →