Optimal Algorithms for Finding the Symmetries of a Planar Point Set

Abstract

This document presents an asymptotically optimal algorithm to locate all the axes of mirror symmetry of a planar point set. The algorithm was derived by reducing the 2-D symmetry problem to linear pattern-matching. Optimal algorithms for finding rotational symmetries and deciding whether a point symmetry exists are also presented. Section 2 of this report contains the algorithm, and section 3 contains proof of why the algorithm works. Section 4 demonstrates that it is impossible to improve the asymptotic time bound. Section 5 presents a variant of the basic algorithm which detects the rotational symmetries and point symmetry, and a proof that these are also optimal.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1985
Accession Number
ADA159625

Entities

People

  • P. T. Highnam

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms
  • Autonomy

DTIC Thesaurus Topics

  • Abstracts
  • Aeronautical Laboratories
  • Air Force
  • Algorithms
  • Alphabets
  • Computer Science
  • Identities
  • Notation
  • Numbers
  • Orientation (Direction)
  • Real Numbers
  • Rotation
  • Symmetry
  • Two Dimensional
  • Universities

Readers

  • Business Analytics
  • Computer Vision.
  • Graph Algorithms and Convex Optimization.