论文标题
关于中间曲线问题的复杂性
On the complexity of the middle curve problem
论文作者
论文摘要
对于一组曲线，Ahn等人。引入了中间曲线的概念，并给出了算法在曲线数中以运行时间指数计算的算法。在这里，我们研究了此问题的计算复杂性：我们表明它是NP完整的，并提供了近似算法。
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.
