Triangulations of Line Segment Sets in the Plane

摘要: Given a set S of line segments in the plane, we introduce new family partitions convex hull called segment triangulations S. The faces such triangulation is maximal disjoint triangles that cut at, and only their vertices. Surprisingly, several properties point extend to triangulations. Thus, number an invariant In same way, if general position, there exists unique whose are inscribable circles interiors do not intersect This triangulation, Delaunay dual Voronoi diagram. main result this paper local optimality which characterizes [10] extends A similar holds for with topology as one.