An optimal bound for high-quality conforming triangulations

This paper shows that, for any plane geometric graph withn vertices, there is a triangulation that conforms to , i.e., each edge of is the union of some edges of , where hasO(n²) vertices with each angle of its triangles measuring no more than 11/15π. Additionally, can be computed inO(n ² logn) time. This research was partially supported by the National University of Singapore under Grant RP940641.