Triangulations with many points of even degree
Jorge Urrutia, Canek Peláez, Adriana Ramírez-Viguer · Canadian Conference on Computational Geometry · 2010
Let S be a set of points in the plane in general position. A triangulation of S will be called even if all the points of S have an even degree. We show how to construct a triangulation of S containing at least b 2n 3 c− 3 points with even degree; this improves slightly the bound of d 2(n 1) 3 e − 6 by Aichholzer et. al. [1]. Our proof can be easily adapted to give, through a long case analysis, triangulations with b 4n 5 c − c vertices with even degree.