Rotationally optimal spanning and Steiner trees in uniform orientation metrics (Q1886240)

The following problem is studied: Find a minimum spanning and Steiner tree for a set of \(n\) points in the plane where the orientations of edge segments are restricted to \(k\) uniformly distributed orientations (\(k = 2, 3, 4,\dots\)) and where the coordinate system can be rotated around the origin by an arbitrary angle. In the case where \(k = 2\), called rectilinear, the edge segments have to be parallel to one of the coordinate axes, while in the case \(k = 4\), called octilinear, the edge segments have to be parallel to one of the coordinate axes or to one of the diagonals. As the coordinate system is rotated, while the points remain stationary, the length and topology of the minimum spanning or Steiner tree changes. A straightforward polynomial-time algorithm is proposed to solve the rotational minimum spanning tree problem. A simple algorithm to solve the rectilinear Steiner tree problem in the rotational setting is also given, as well as a finite time algorithm for the general Steiner tree problem with \(k\) uniform orientations.