The Complexity of Manipulating Hierarchically Defined Sets of Rectangles.

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 O(N lg N) algorithms that process inputs obeying certain restrictions. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1981
Accession Number
ADA106552

Entities

People

  • Jon Louis Bentley
  • Thomas Ottmann

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Computer Graphics
  • Computer Science
  • Computers
  • Construction
  • Geometric Forms
  • Geometry
  • Graphics
  • Language
  • Military Research
  • Models
  • Motivation
  • Polynomials
  • Symbols
  • Two Dimensional
  • Universities

Fields of Study

  • Computer science

Readers

  • Computer Science.
  • Educational Psychology
  • Operations Research