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
Distribution Statement : APPROVED FOR PUBLIC RELEASE