The geometry of inner spanning trees for planar polygons
Alexandr O Ivanov, Alexey Avgustinovich Tuzhilin · Izvestiya Mathematics · 2012
We study the geometry of minimal inner spanning trees for planar polygons (that is, spanning trees whose edge-intervals lie in these polygons). We construct analogues of Voronoi diagrams and Delaunay triangulations, prove that every minimal inner spanning tree is a subgraph of an appropriate Delaunay triangulation, and describe the possible structure of the cells of such triangulations.