The geometry of inner spanning trees for planar polygons

A. O. Ivanov^ab, A. A. Tuzhilin<sup>ab

a</sup> P. G. Demidov Yaroslavl State University
^b M. V. Lomonosov Moscow State University

Abstract: 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.

Keywords: inner spanning tree, planar polygon, Euclidean spanning tree, Voronoi diagram, Delaunay triangulation, Steiner ratio, characteristic domain.

UDC: 514.77+512.816.4+517.924.8

MSC: 05C05, 05C35, 51M16, 52B05, 68R10

Received: 28.12.2010
Revised: 08.08.2011

DOI: 10.4213/im6595

 English version: Izvestiya: Mathematics, 2012, 76:2, 215–244

Bibliographic databases:

• 
• 
• 
• 
• 
• 
•