### Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 719-722 |

Number of pages | 4 |

Journal | Pattern Recognition Letters |

Volume | 14 |

Issue number | 9 |

DOIs | |

State | Published - Sep 1993 |

### ASJC Scopus subject areas

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

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

## Cite this

ElGindy, H., Everett, H., & Toussaint, G. (1993). Slicing an ear using prune-and-search.

*Pattern Recognition Letters*,*14*(9), 719-722. https://doi.org/10.1016/0167-8655(93)90141-Y