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. CMUCS81109. 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 NPhard 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 
Contenttype: text/plain

last changed 
2003/06/02 08:24 
