Geometrische Probleme, die in

37

Eine Reihe von geometrischen Problemen ist in einfach , in für jedoch NP-vollständig (einschließlich eines meiner Lieblingsprobleme, Einheitsplattenabdeckung). $R^1$ $R^d$ $d\geq2$

Kennt jemand ein Problem, das für und polyzeitlösbar , für jedoch NP-vollständig ist ? $R^1$ $R^2$ $R^d,d\geq3$

Gibt es allgemeiner Probleme, die für NP-vollständig, für jedoch polyzeitlösbar sind , wobei ? $R^k$ $R^{k-1}$ $k\geq3$

cc.complexity-theory reference-request cg.comp-geom Bob Fraser
quelle

Ist dreidimensionales Matching geometrisch?

Jukka Suomela

1

nicht wirklich. das "3-dimensionale" ist im kartesischen und nicht im euklidischen Sinne.

Suresh Venkat

25

Deckung durch halbe Lücken setzen.

Wenn eine Menge von Punkten in der Ebene gegeben ist und eine Menge von Halbebenen berechnet wird, kann die minimale Anzahl von Halbebenen, die die Punktmengen abdecken, in Polynomzeit in der Ebene gelöst werden. Das Problem ist jedoch NP schwer in 3d (es ist schwieriger als eine minimale Deckung durch eine Teilmenge von Scheiben mit Punkten in 2d zu finden). In 3d erhalten Sie eine Teilmenge von Halbräumen und Punkten, und Sie suchen nach einer minimalen Anzahl von Halbräumen, die die Punkte abdecken.

Der Polytime-Algorithmus in 2d wird hier beschrieben: http://valis.cs.uiuc.edu/~sariel/papers/08/expand_cover/

Sariel Har-Peled
quelle

Es ist mir ein bisschen peinlich, dass ich dieses Ergebnis nicht kenne, da es den Problemen, an denen ich arbeite, sehr nahe kommt :-) Dies ist auch genau die Art von Antwort, auf die ich gehofft habe. Wenn Sie sagen, es ist schwieriger als die Festplattenabdeckung in 2D, meine ich, dass es APX-schwer ist?

Bob Fraser

1

Das 2d-Problem ist das Polynom. Der andere ist NP-Hard. Allerdings glaube ich nicht, dass das 3D-Problem APX schwer ist. Es gibt gute Gründe zu glauben, dass ein PTAS über die lokale Suche möglich sein könnte ...

Sariel Har-Peled

... und mit härter meinte ich, dass das Festplattenproblem in 3D auf das Problem der halben Speicherplätze angehoben (dh reduziert) werden kann.

Sariel Har-Peled

29

Es ist nicht ganz das, wonach Sie fragen, denn die 3D-Version ist noch schwieriger als NP-vollständig, aber: Das Finden eines kürzesten Pfades zwischen zwei Punkten unter polygonalen Hindernissen in der Ebene erfolgt in Polynomzeit (am einfachsten erstellen Sie den Sichtbarkeitsgraphen der beiden Terminals und die Polygonscheitelpunkte und wenden Dijkstra an; es gibt auch einen komplizierteren O (n log n) -Algorithmus aufgrund von Hershberger und Suri, SIAM J. Comput. 1999), aber das Finden eines kürzesten Pfades unter polyedrischen Hindernissen in 3d ist PSPACE-vollständig (Canny und Reif, FOCS 1987).

David Eppstein
quelle

10

Sind Sie sich über den Planarfall sicher? Die Algorithmen, die Sie zitieren, erfordern grundsätzlich eine exakte reelle Arithmetik! cstheory.stackexchange.com/questions/4034/…

Jeffs

Äh. Guter Punkt. Und ich kann nicht mit Fließkomma und Approximation davonkommen, weil das 3D-Problem gut approximiert werden kann. Hoppla. Ich denke, es gibt einen "exakten reellen arithmetischen" Sinn, in dem das eine Polynom ist und das andere schwer, aber Sie haben Recht, das ist ein anderer Weg, in dem die Frage nicht beantwortet wird.

David Eppstein

6

Das ist wirklich interessant. Die Summe der Quadratwurzelprobleme ergibt eine Reihe von Problemen in cg, bei denen das Problem mit Ausnahme dieser Details leicht zu lösen wäre. Es ist in gewisser Weise großartig, weil es eines dieser Probleme ist, das man braucht, um die Leute davon zu überzeugen, dass es schwierig ist. Danke für die Hinweise.

Bob Fraser

20

Jedes nicht konvexe Polygon in der Ebene kann in O (n) -Zeit ohne Steiner-Punkte trianguliert werden. Das heißt, jeder Scheitelpunkt der Triangulation ist ein Scheitelpunkt des Polygons. Außerdem hat jede Triangulation genau n-2 Dreiecke.

Die Bestimmung, ob ein nichtkonvexes Polyeder in R ^ 3 ohne Steiner-Punkte trianguliert werden kann, ist NP-vollständig. Das Ergebnis der NP-Härte ist auch dann gültig, wenn Sie eine Triangulation mit einem Steiner-Punkt erhalten. Daher ist auch die Annäherung an die erforderliche Mindestanzahl von Steiner-Punkten NP-hart. [Jim Ruppert und Raimund Seidel. Über die Schwierigkeit, dreidimensionale nichtkonvexe Polyeder zu triangulieren. Discrete Comput. Geom. 1992.]

Wenn das gegebene Polyeder konvex ist, ist das Finden einer Triangulation einfach, aber das Finden der Triangulation mit der minimalen Anzahl von Tetraedern ist NP-hart. [Alexander Below, Jesús de Loera und Jürgen Richter-Gebert. Die Komplexität, kleine Triangulationen von konvexen 3-Polytopen zu finden . J. Algorithms 2004.]

Jeffε
quelle

2

Danke für die Hinweise, Jeff. Insbesondere halte ich das letzte von Ihnen erwähnte Ergebnis für interessant. Es ist ein bisschen überraschend, dass die Anzahl der Simplices, aus denen das Polygon besteht, in der Ebene konstant ist, dies jedoch nicht mehr in höheren Dimensionen gilt und tatsächlich schwer zu optimieren ist. Das ist genau die Antwort, auf die ich gehofft habe.

Bob Fraser

16

$d$ $d \le 3$ $d \ge 4$

Yoshio Okamoto
quelle

2

\exists R

$\exists\mathbb{R}$

Ich hatte dieses Problem noch nie gesehen, danke.

Bob Fraser

Wiederum, wie David Eppsteins Antwort, härter (wahrscheinlich) als NP-vollständig.

Peter Shor

11

Es ist einfach zu entscheiden, ob ein metrischer Raum isometrisch in R ^ 2 eingebettet werden kann. Es ist jedoch schwer, sich für die Einbettbarkeit von R ^ 3 zu entscheiden.

$\ell_\infty^2$ $\ell_\infty^3$

Papier

Zouzias
quelle

Das ist auch ein gutes Beispiel.

Suresh Venkat

-2

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

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

Kaushik Shankar
quelle

Was bedeutet es zu sagen, dass 2SAT "in" R ^ 2 ist?

Suresh Venkat

R^{2}

$R^2$

11

-1: Ich sehe nicht, wie 2SAT in R ^ 2 ist. Ich verstehe nicht, wie 2SAT ein "geometrisches Problem" ist.

Robin Kothari

Ich entschuldige mich dafür, dass ich kein geometrisches Problem präsentiere, aber obwohl der Titel nach geometrischen Problemen fragt, geben die beiden Fragen in den Kommentaren nicht an, dass es sich um ein geometrisches Problem handelt. Darüber hinaus hat die 2-Erfüllbarkeit eine grafische Darstellung, die als 2-dimensionale Übereinstimmung, dh in P, bekannt ist, wobei als 3-Erfüllbarkeit der 3-dimensionalen Übereinstimmung entspricht, die NP ist.

Kaushik Shankar

@ Robin Ich ging voran und erklärte in meinem ursprünglichen Kommentar.

Kaushik Shankar

Geometrische Probleme, die in

Antworten: