Accession Number : ADA058768

Title :   Algorithms for Reporting and Counting Geometric Intersections.

Descriptive Note : Interim rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Bentley,Jon L. ; Ottmann,Th.

Report Date : AUG 1978

Pagination or Media Count : 20

Abstract : An interesting class of Geometric Intersection Problems calls for dealing with the pairwise intersections among a set of N objects in the plane. These problems arise in many applications such as printed circuit design, architectural data bases, and computer graphics. Shamos and Hoey have described a number of algorithms for detecting if any two objects in a planar set intersect. This paper extends this work by giving algorithms which count the number of such intersections and algorithms which report all such intersections.

Descriptors :   *COMBINATORIAL ANALYSIS, COMPUTER ARCHITECTURE, COMPUTER GRAPHICS, PRINTED CIRCUITS, CROSSINGS, COUNTERS.

Subject Categories : Theoretical Mathematics
      Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE