¿Problemas geométricos que son NP completos en

Una serie de problemas geométricos son fáciles cuando se consideran en , pero son NP-completos en para (incluido uno de mis problemas favoritos, la cubierta del disco de la unidad).$R^1$$R^d$$d\geq2$

¿Alguien sabe de un problema que pueda resolverse en polytime para y , pero NP-complete para ? $R^1$$R^2$$R^d,d\geq3$

En términos más generales, ¿existen problemas que son NP completos para pero polytime solucionables para , donde ?$R^k$$R^{k-1}$$k\geq3$

Establecer cubierta por medio espacios.

Dado un conjunto de puntos en el plano, y un conjunto de medios planos que calculan el número mínimo de medios planos que cubren los conjuntos de puntos se puede resolver en tiempo polinómico en el plano. Sin embargo, el problema es que NP es difícil en 3d (es más difícil que encontrar una cobertura mínima por subconjunto de discos de puntos en 2d). En 3d se le da un subconjunto de medios espacios y puntos, y está buscando un número mínimo de medios espacios que cubran los puntos.

El algoritmo polytime en 2d se describe aquí: http://valis.cs.uiuc.edu/~sariel/papers/08/expand_cover/

No es exactamente lo que pides, porque la versión en 3D es aún más difícil que NP-complete, pero: encontrar el camino más corto entre dos puntos entre obstáculos poligonales en el plano es en tiempo polinómico (lo más simple, construye el gráfico de visibilidad de los dos terminales y los vértices poligonales y aplican Dijkstra; también hay un algoritmo O (n log n) más complicado debido a Hershberger y Suri, SIAM J. Comput. 1999), pero encontrar el camino más corto entre los obstáculos poliédricos en 3D es completo para PSPACE (Canny y Reif, FOCS 1987).

Cualquier polígono no convexo en el plano puede triangularse en tiempo O (n) sin puntos Steiner; es decir, cada vértice de la triangulación es un vértice del polígono. Además, cada triangulación tiene exactamente n-2 triángulos.

Sin embargo, determinar si un poliedro no convexo en R ^ 3 se puede triangular sin puntos Steiner es NP-completo. El resultado de dureza NP se mantiene incluso si se le da una triangulación con un punto Steiner, por lo que incluso aproximar el número mínimo de puntos Steiner necesarios es NP-duro. [Jim Ruppert y Raimund Seidel. Sobre la dificultad de triangular poliedros no convexos tridimensionales. Computación discreta. Geom 1992.]

Si el poliedro dado es convexo, encontrar una triangulación es fácil, pero encontrar la triangulación con el número mínimo de tetraedros es NP-duro. [Alexander debajo, Jesús de Loera y Jürgen Richter-Gebert. La complejidad de encontrar pequeñas triangulaciones de 3-politopos convexos . J. Algorithms 2004.]

El problema de realizabilidad para los politopos -dimensionales es un candidato. Cuando d ≤ 3 , es solucionable en tiempo polinómico (según el teorema de Steinitz ), pero cuando d ≥ 4 , esto es NP-duro. Para obtener más información, consulte "Los espacios de realización de 4-polytopes son universales " de Richter-Gebert y Ziegler (también hay una versión arxiv ), y el libro " Lectures on Polytopes " (segunda impresión) de Ziegler.$d$$d \le 3$$d \ge 4$

Decidir si un espacio métrico es isométricamente incrustable en R ^ 2 es fácil. Sin embargo, es NP-difícil decidir por la integración de R ^ 3.

Incrustar en es fácil, incrustar en ℓ 3 $\ell_\infty^2$$\ell_\infty^3$ es NP-completo. Jeff Edmonds. SODA 2007

Papel

$R^2$$R^3$$Z^2$$Z^3$

$k = 2$$Z^2$$Z^k$$k > 2$.