Accession Number:

ADA106552

Title:

The Complexity of Manipulating Hierarchically Defined Sets of Rectangles.

Descriptive Note:

Interim rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Bentley,Jon Louis
• Ottmann,Thomas

Report Date:

1981-04-01

Pagination or Media Count:

43.0

Abstract:

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 we 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. We will see that while most of the problems are NP-hard in the general case, there are ON lg N algorithms that process inputs obeying certain restrictions. Author

Descriptors:

• *COMPUTER AIDED DESIGN
• *INTEGRATED CIRCUITS
• *RECTANGULAR BODIES
• MATHEMATICAL MODELS
• ALGORITHMS
• INPUT
• DATA MANAGEMENT
• PARAMETERS
• COMPUTER GRAPHICS
• EXPONENTIAL FUNCTIONS
• HIERARCHIES

Subject Categories:

• Electrical and Electronic Equipment

Distribution Statement:

APPROVED FOR PUBLIC RELEASE