  In the Continuous Steiner Tree problem (CST), we are given as input a set of
points (called terminals) in a metric space and ask for the minimum-cost tree
connecting them. Additional points (called Steiner points) from the metric
space can be introduced as nodes in the solution. In the Discrete Steiner Tree
problem (DST), we are given in addition to the terminals, a set of facilities,
and any solution tree connecting the terminals can only contain the Steiner
points from this set of facilities. Trevisan [SICOMP'00] showed that CST and
DST are APX-hard when the input lies in the $\ell_1$-metric (and Hamming
metric). Chleb\'ik and Chleb\'ikov\'a [TCS'08] showed that DST is NP-hard to
approximate to factor of $96/95\approx 1.01$ in the graph metric (and
consequently $\ell_\infty$-metric). Prior to this work, it was unclear if CST
and DST are APX-hard in essentially every other popular metric!
  In this work, we prove that DST is APX-hard in every $\ell_p$-metric. We also
prove that CST is APX-hard in the $\ell_{\infty}$-metric. Finally, we relate
CST and DST, showing a general reduction from CST to DST in $\ell_p$-metrics.
As an immediate consequence, this yields a $1.39$-approximation polynomial time
algorithm for CST in $\ell_p$-metrics.
