Finding the Contour of a Union of Iso-Oriented Rectangles.

Abstract

Let R(1),...,R(m) be rectangles on the plane with sides parallel to the coordinate axes. An algorithm is described to find the contour of F = R(1) U ... U R(m) in o(mlogm + plog(2 sq m/p)) time, where p is the number of edges in the contour. This is o(sq. m) (optimal) in the general case, and o(mlogm) (optimal) when F is without holes (then p < or = 8m-4). (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1979
Accession Number
ADA084959

Entities

People

  • Franco P. Preparata
  • Witold Lipski Jr.

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Air Platforms
  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Boundaries
  • Computer Graphics
  • Geometry
  • Graphics
  • Illinois
  • Intervals
  • Large Scale Integration
  • Numbers
  • Real Numbers
  • Sequences
  • Trees (Data Structures)
  • Two Dimensional
  • United States
  • United States Government
  • Very Large Scale Integration

Readers

  • Graph Algorithms and Convex Optimization.