Komplexität des versteckten Polygon-Puzzles auf quadratischen Gittern?

10

Hiroimono ist ein beliebtes vollständiges Puzzle. Ich interessiere mich für die rechnerische Komplexität eines verwandten Puzzles.NP

Das Problem ist:

Eingabe : Gegeben eine Menge von Punkten auf einem x n quadratischen Gitter und einer ganzen Zahl knnk

Frage : Gibt es ein geradliniges Polygon (dessen Seiten parallel zur oder y- Achse sind), sodass die Anzahl der Punkte an den Ecken des Polygons mindestens k beträgt ?xyk

Jede Ecke des Polygons muss sich an einem der Eingabepunkte befinden (Biegungen sind also nur an einem Eingabepunkt zulässig).

Was ist die Komplexität dieses Problems? Was ist die Komplexität, wenn sich die Lösung auf konvexe geradlinige Polygone beschränkt?

EDIT 13. April: Alternative Formulierung: Finden Sie ein geradliniges Polygon mit den maximalen Ecken an den angegebenen Punkten.

Mohammad Al-Turkistany
quelle
4
Sollten konvexe geradlinige Polygone nicht durch dynamische Programmierung in Polynomzeit lösbar sein?
Peter Shor
4
Ja, das sollte es.
Jeffs
@ JeffE, wie wäre es mit dem allgemeinen nicht konvexen Fall? Was ist deine Neigung?
Mohammad Al-Turkistany
2
Für viele dieser Probleme ist es am besten, mit etwas wie planarem 3SAT oder sogar planarem NAE-SAT zu beginnen. Es wird schrecklich hässlich sein, aber die Planarität gibt Ihnen die Strukturen, die Sie benötigen könnten.
Suresh Venkat
5
@Suresh Nur eine Anmerkung: googeln Ich fand heraus, dass die planare Version von NAE3SAT in P ( portal.acm.org/… ) ist.
Marzio De Biasi

Antworten:

6

3yx

Das Knoten-Gadget ist in der folgenden Abbildung dargestellt:

Geben Sie hier die Bildbeschreibung ein

[W,N,E]C×CC2C2C+2C×C4+6[N,E,S][E,S,W][S,W,N]

(x1,y1),(x2,y2)x1x2y1y24×3

Geben Sie hier die Bildbeschreibung ein

EW

Geben Sie hier die Bildbeschreibung ein

4+2C2e

neC>(4n+2e)k=2Cn

Marzio De Biasi
quelle
5

V

Zweitens gibt es ein schönes Update zu dieser Arbeit von Maarten Löffler und Elena Mumford in einem Artikel, " Connected Rectilinear Graphs on Point Sets ", Journal of Computational Geometry , 2 (1), 1–15, 2011. Aus ihrer Zusammenfassung:

V

Joseph O'Rourke
quelle