The Polygon Containment Problem

Abstract

One feature of pattern recognition is to treat geometric objects as physical entities. This approach, also found in many applications areas, gives rise to a host of problems that essentially involve matching a mobile object against a static one. This article investigates the particular problem of determining whether a given polygon P (with p vertices) can fit into a polygon Q (with q vertices), if translations and/or rotations are allowed. The main result is an O(pq2) algorithm for solving this problem, for the case where Q is convex. We also give an O(p + q) procedure, valid if only translations are allowed; and we show that the naive algorithm for the general problem requires as much as O[p3q3(p + q) log(p + q)].

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1983
Accession Number
AD1116582

Entities

People

  • Bernard Chazelle

Organizations

  • Defense Advanced Research Projects Agency

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Boundaries
  • Cells
  • Instructions
  • Intervals
  • Lists (Data Structures)
  • Numbers
  • Pattern Recognition
  • Polygons
  • Real Numbers
  • Rotation
  • Sequences
  • Time Intervals
  • Translations
  • Triangles
  • Vector Spaces

Fields of Study

  • Mathematics

Readers

  • Computer Vision.
  • Graph Algorithms and Convex Optimization.

Technology Areas

  • AI & ML
  • AI & ML - Machine Learning Algorithms