1979/09/01 by Bentley, Ottmann · 6 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Robotic Path Planning Algorithms #Intersection (aeronautics) #Computer science #Set (abstract data type) #Graphics #Pairwise comparison #Class (philosophy) #Planar #Computer graphics #Theoretical computer science #Computational geometry #Plane (geometry) #Algorithm #Computer graphics (images) #Artificial intelligence #Mathematics #Programming language #Geometry
paper · doi:10.1109/tc.1979.1675432
openalex publication_date 1979/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22
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 whether any two objects in a planar set intersect. In this paper we extend their work by giving algorithms that count the number of such intersections and algorithms that report all such intersections.