An efficient algorithm for decomposing a polygon into star-shaped polygons

Research output: Contribution to journalArticle

Abstract

In this paper we show how a theorem in plane geometry can be converted into a O(n log n) algorithm for decomposing a polygon into star-shaped subsets. The computational efficiency of this new decomposition contrasts with the heavy computational burden of existing methods.

Original languageEnglish (US)
Pages (from-to)395-398
Number of pages4
JournalPattern Recognition
Volume13
Issue number6
DOIs
StatePublished - 1981

    Fingerprint

Keywords

  • Colouring algorithms
  • Computational geometry
  • Polygonal decomposition
  • Star-shaped polygons
  • Syntactic pattern recognition
  • Triangulation

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence

Cite this