SLICING AN EAR USING PRUNE-AND-SEARCH

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 foun d by first triangulating P and subsequently searching the triangulatio n. However, although a polygon can be triangulated in linear time, suc h 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 wit h a simple, practically efficient algorithm that does not require pre- triangulating P.