Minimum Feature Size in Proper Triangulations

Abstract

Triangulating a polygon can introduce distances between vertices and nonincident edges that are much smaller than those in the input. The minimum feature size of a crossing-free geometric graph is the smallest distance between a vertex and a nonincident edge. This measure applies to both a polygon and its triangulations, and the ratio of the input minimum feature size to that of the triangulation is the degradation. Even when Steiner vertices are allowed, some degradation remains unavoidable for proper triangulations, in which every bounded face has exactly three edges on its boundary. We prove that, for every sufficiently large N, there is an N-vertex polygon P such that every proper triangulation G of P has degradation Ω(log N). The bound holds even when any finite number of Steiner vertices may be added in the bounded face of P and on any of its edges. Together with the known O(log N) upper bound, it establishes that the worst-case optimal degradation for proper triangulations of N-vertex polygons is Θ(log N). These polygons can also be chosen so that achieving O(log N) degradation requires Ω(N) Steiner vertices. This matches the known O(N) upper bound on the number of Steiner vertices.