On the Restricted $k$-Steiner Tree Problem

Prosenjit Bose, Anthony D'Angelo, Stephane Durocher

Given a set $P$ of $n$ points in ${\mathbb{R}}^2$ and an input line $\gamma$ in ${\mathbb{R}}^2$, we present an algorithm that runs in optimal $\Theta (n\log n)$ time and $\Theta (n)$ space to solve a…