On the complexity of minimum-link path problems
On the complexity of minimum-link path problems
复制标题
最小链路路径问题的复杂性
DOI：
10.20382/jocg.v8i2a5
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
F. Staals
中科院分区：
文献类型：
--
作者：
I. Kostitsyna;M. Löffler;V. Polishchuk;F. Staals
我们重新审视最小连接路径问题：给定一个多面体域和其中的两个点，通过具有最少边数的多边形路径连接这些点。我们考虑设置的顶点和/或边缘的路径被限制躺在域的边界上，或者可以在其内部。我们的研究结果包括位复杂性的界限，一个新的一般硬度建设，和多项式时间近似计划。我们充分表征的情况下，在2维，并提供第一个结果在3维及更高的几个变种的问题。具体地说，我们的研究结果解决了几个开放的问题。我们证明，计算最小链接漫反射路径，在计算机图形学中的光线跟踪的动机，是NP-难的，即使是二维多边形域的孔。这仍然是一个悬而未决的问题[Ghosh et al. [2012年10月]在这方面做了大量的工作。我们还解决了[Mitchell et al.’1992]在手册[Goodman and Rourke’2004]（参见第27.5章，开放问题3）和开放问题项目[http：//maven.smith.edu/Rourke/TOPP/]（参见问题22）中提到：“3-空间中最小链路路径问题的复杂性是多少？“我们的结果意味着，即使在地形上，这个问题也是NP困难的（因此，由于答案的离散性，除非P=NP，否则没有FPTAS），但允许PTAS。
We revisit the minimum-link path problem: Given a polyhedral domain and two points in it, connect the points by a polygonal path with minimum number of edges. We consider settings where the vertices and/or the edges of the path are restricted to lie on the boundary of the domain, or can be in its interior. Our results include bit complexity bounds, a novel general hardness construction, and a polynomial-time approximation scheme. We fully characterize the situation in 2 dimensions, and provide first results in dimensions 3 and higher for several variants of the problem. Concretely, our results resolve several open problems. We prove that computing the minimum-link diffuse reflection path, motivated by ray tracing in computer graphics, is NP-hard, even for two-dimensional polygonal domains with holes. This has remained an open problem [Ghosh et al.'2012] despite a large body of work on the topic. We also resolve the open problem from [Mitchell et al.'1992] mentioned in the handbook [Goodman and Rourke'2004] (see Chapter 27.5, Open problem 3) and The Open Problems Project [http://maven.smith.edu/~orourke/TOPP/] (see Problem 22): "What is the complexity of the minimum-link path problem in 3-space?" Our results imply that the problem is NP-hard even on terrains (and hence, due to discreteness of the answer, there is no FPTAS unless P=NP), but admits a PTAS.