¿Problemas geométricos que son NP completos en

37

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).R1Rdd2

¿Alguien sabe de un problema que pueda resolverse en polytime para y , pero NP-complete para ? R1R2Rd,d3

En términos más generales, ¿existen problemas que son NP completos para pero polytime solucionables para , donde ?RkRk1k3

Bob Fraser
fuente
¿La coincidencia tridimensional es geométrica?
Jukka Suomela
1
realmente no. el "tridimensional" está en sentido cartesiano, no euclidiano.
Suresh Venkat

Respuestas:

25

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/

Sariel Har-Peled
fuente
Estoy un poco avergonzado de no saber este resultado, dado lo cerca que está de los problemas en los que trabajo :-) Esta también es exactamente la clase de respuesta que esperaba. Cuando dices que es más difícil que la cubierta del disco en 2D, ¿supongo que quieres decir que es APX-hard?
Bob Fraser
1
El problema 2d es polinomial. El otro es NP-Hard. Sin embargo, no creo que el problema 3d sea APX difícil. Hay buenas razones para creer que un PTAS podría ser posible, a través de la búsqueda local ...
Sariel Har-Peled
... y con más fuerza quise decir que el problema del disco se puede elevar (es decir, reducir) al problema de los medios espacios en 3d.
Sariel Har-Peled
29

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).

David Eppstein
fuente
10
¿Estás seguro del caso plano? ¡Los algoritmos que usted cita requieren fundamentalmente una aritmética real exacta! cstheory.stackexchange.com/questions/4034/…
Jeffε
Er. Buen punto. Y no puedo salir de eso diciendo que use punto flotante y aproximado, porque el problema 3d puede ser muy aproximado. Ups Supongo que hay un sentido de "aritmética real exacta" en el que uno es polinomial y el otro es difícil, pero aún así, tienes razón, esa es otra forma en que no responde la pregunta.
David Eppstein
66
Esto es realmente interesante El problema de la suma de las raíces cuadradas se convierte en una serie de problemas en cg donde el problema sería fácil, excepto por este detalle. Es genial de alguna manera, porque es uno de estos problemas que debes convencer a la gente de que es difícil. Gracias por los consejos.
Bob Fraser
20

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.]

Jeffε
fuente
2
Gracias por los consejos, Jeff. En particular, creo que el último resultado que mencionas es interesante. Es un poco sorprendente que mientras esté en el plano, el número de simplificaciones que componen el polígono es una constante, pero esto ya no se mantiene en dimensiones más altas y, de hecho, es difícil de optimizar. Este es exactamente el tipo de respuesta que esperaba.
Bob Fraser
16

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.dd3d4

Yoshio Okamoto
fuente
2
Más específicamente que decir que es NP-hard, está completo para , la teoría existencial de los números reales. R
David Eppstein
No había visto este problema antes, gracias.
Bob Fraser
De nuevo, como la respuesta de David Eppstein, más difícil (probablemente) que NP-complete.
Peter Shor
11

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 23 es NP-completo. Jeff Edmonds. SODA 2007

Papel

Zouzias
fuente
Ese también es un buen ejemplo.
Suresh Venkat
-2

R2R3Z2Z3

k=2Z2Zkk>2.

Kaushik Shankar
fuente
¿Qué significa decir que 2SAT está "en" R ^ 2?
Suresh Venkat
R2
11
-1: No veo cómo está 2SAT en R ^ 2. No veo cómo 2SAT es un "problema geométrico".
Robin Kothari
Pido disculpas por no presentar un problema geométrico, pero aunque el título pregunta sobre problemas geométricos, las dos preguntas en los comentarios no especifican que sea geométrico. Además, la satisfacción de 2 tiene una representación gráfica conocida como coincidencia bidimensional, es decir, en P, donde la satisfacción de 3 corresponde con la coincidencia tridimensional, que es NP.
Kaushik Shankar
@ Robin seguí adelante y aclaré en mi comentario original.
Kaushik Shankar