property, and repeatedly removing an ear from the queue and updating the adjacent triples, it is possible to perform ear-clipping in time , where is the number of input vertices and is the number of reflex vertices.

If a simple polygon is triangulated, then a triple of consecutive vertices forms an ear if is a convex vertex and none of its other neighbors in the triangulation lie in triangle . By testing all neighbors of all vertices, it is possible to find all the ears of a triangulated simple polygon in linear time.