ISSN:
1436-5057
Keywords:
68Q25
;
68U05
;
Rectangles
;
balanced cuts
;
separation
;
binary space partition
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Gegeben sei eine Menge vonn (ggf. überlappenden) isothetischen Hyperrechtecken imd-dimensionalen Raum. Diese Arbeit beschäftigt sich mit Zerlegungen dieser Hyperrechteckmenge durch Schnitthyperebenen, wobei wir annehmen, daß jedes von einer Hyperebene geschnittene Hyperrechteck in zwei nicht-überlappende Hyperrechtecke zerschnitten wird. Wir untersuchen das Verhalten einiger Balancierungskriterien für Schnitte und präsentieren optimale and praktikable Algorithmen zur Berechnung der entsprechenden balancierten Schnitte. Schließlich geben wir auch scharfe Worst-case-Schranken für die bestmöglich erreichbare Qualität der balancierten Schnitte an.
Notes:
Abstract We are given a set ofn 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02238431
Permalink