  For a set of curves, Ahn et al. introduced the notion of a middle curve and
gave algorithms computing these with run time exponential in the number of
curves. Here we study the computational complexity of this problem: we show
that it is NP-complete and give approximation algorithms.
