Plane-Sweep Algorithms for Intersecting Geometric Figures,

Abstract

This report considers various types of geometric figures in the plane defined by points connected by straight line segments, such as polygons (not necessarily simple) and maps (embedded planar graphs); and the problem of computing the intersection of such figures by means of a 'greedy' type of algorithm that sweeps the plane unidirectionally. Let n be the total number of points of all the figures involved, and s the total number of intersections of line segments. It is shown in the general case (no converity) a previously known algorithm can be extended to compute in time O((n+s)logn) and space O(n+s) all the connected regions into which the plane is divided by intersecting the figures. When the regions of each figure are convex, the same can be achieved in time O(nlogn+s) and space O(n).

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1979
Accession Number
ADA085319

Entities

People

  • Franco P. Preparata
  • J. Nievergelt

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Buildings And Structures
  • Computational Complexity
  • Computational Science
  • Concrete
  • Contracts
  • Data Processing
  • Electronics
  • Geometry
  • Governments
  • Illinois
  • Intervals
  • Plane Geometry
  • Security
  • Transitions
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.

Technology Areas

  • Space
  • Space - Space Objects