Algorithms for Reporting and Counting Geometric Intersections.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1978
Accession Number
ADA058768

Entities

People

  • Jon L. Bentley
  • Th. Ottmann

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Circuit Boards
  • Circuits
  • Computer Graphics
  • Computer Science
  • Computers
  • Databases
  • Graphics
  • Integrated Circuits
  • Lists (Data Structures)
  • Observation
  • Operations Research
  • Printed Circuit Boards
  • Printed Circuits

Fields of Study

  • Computer science
  • Engineering

Readers

  • Graph Algorithms and Convex Optimization.