Slicing an ear using prune-and-search

Hossam ElGindy, Hazel Everett, Godfried Toussaint

Research output: Contribution to journalArticlepeer-review


It is well known that a diagonal of a simple polygon P can be found in linear time with a simple and practically efficient algorithm. An ear of P is a triangle such that one of its edges is a diagonal of P and the remaining two edges are edges of P. An ear of P can easily be found by first triangulating P and subsequently searching the triangulation. However, although a polygon can be triangulated in linear time, such a procedure is conceptually difficult and not practically efficient. In this note we show that an ear of P can be found in linear time with a simple, practically efficient algorithm that does not require pre-triangulating P.

Original languageEnglish (US)
Pages (from-to)719-722
Number of pages4
JournalPattern Recognition Letters
Issue number9
StatePublished - Sep 1993

ASJC Scopus subject areas

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


Dive into the research topics of 'Slicing an ear using prune-and-search'. Together they form a unique fingerprint.

Cite this