  The 1-Steiner tree problem, the problem of constructing a Steiner minimum
tree containing at most one Steiner point, has been solved in the Euclidean
plane by Georgakopoulos and Papadimitriou using plane subdivisions called
oriented Dirichlet cell partitions. Their algorithm produces an optimal
solution within $O(n^2)$ time. In this paper we generalise their approach in
order to solve the $k$-Steiner tree problem, in which the Steiner minimum tree
may contain up to $k$ Steiner points for a given constant $k$. We also extend
their approach further to encompass other normed planes, and to solve a much
wider class of problems, including the $k$-bottleneck Steiner tree problem and
other generalised $k$-Steiner tree problems. We show that, for any fixed $k$,
such problems can be solved in $O(n^{2k})$ time.
