CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design
supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

authors Bentley, Jon L. and Ottmann, Thomas
year 1981
title The Complexity of Manipulating Hierarchically Defined Sets of Rectangles
source 40 p. : ill. Pittsburgh, PA: Department of Computer Science, CMU., April, 1981. CMU-CS-81-109. includes bibliography
summary Algorithms that manipulate sets of rectangles are of great practical importance in VLSI design systems and other applications. Although much theoretical work has appeared recently on the complexity of rectangle problems, it has assumed that the inputs are given as a list of rectangles. In this paper the authors study the complexity of rectangle problems when the inputs are given in a hierarchical language that allows the designer to build large designs by replicating small designs. They show that while most of the problems are NP-hard in the general case, there are O(N log N) algorithms that process inputs obeying certain restrictions
keywords rectangles, algorithms, computational geometry, data structures
series CADline
references Content-type: text/plain
last changed 2003/06/02 08:24
HOMELOGIN (you are user _anon_873863 from group guest) Works Powered by SciX Open Publishing Services 1.002