ON OPTIMAL CUTS OF HYPERRECTANGLES

被引：4

作者：

DAMORE, F ^{[1
]}

NGUYEN, NVH ^{[1
]}

ROOS, T ^{[1
]}

WIDMAYER, P ^{[1
]}

机构：

[1] ETH ZENTRUM,DEPT INFORMAT,CH-8092 ZURICH,SWITZERLAND

来源：

COMPUTING | 1995年 / 55卷 / 03期

关键词：

RECTANGLES; BALANCED CUTS; SEPARATION; BINARY SPACE PARTITION;

D O I：

10.1007/BF02238431

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We are given a set of n d-dimensional (possibly intersecting) isothetic hyperrectangles. The topic of this paper is the separation of these rectangles by means of a cutting isothetic hyperplane. Thereby we assume that a rectangle which is intersected by the cutting plane iscut into two non-overlapping hyperrectangles. We investigate the behavior of several kinds of balancing functions, as well as their linear combination and present optimal and practical algorithms for computing the corresponding balanced cuts. In addition, we give tight worst-case bounds for the quality of the balanced cuts.

引用

页码：191 / 206

页数：16

共 19 条

[1]

AMATODES JA, 1990, COMP GRAPHICS, V24, P115

[2] MULTIDIMENSIONAL BINARY SEARCH TREES USED FOR ASSOCIATIVE SEARCHING [J].