next up previous contents
Next: Klauseln. Up: Das Kunstausstellungsproblem ist NP-hart Previous: Das Kunstausstellungsproblem ist NP-hart

Literale.

Jedes Literal wird zu einem so genannten Literalmuster, wie in Abbildung A.4 dargestellt. Der Punkt $ p$ ist von Punkt $ f$ und Punkt $ t$ aus sichtbar. Das gesamte Polygon ist so konstruiert, dass Punkt $ p$ von keinem anderen Eckpunkt aus zu sehen ist. Am Punkt $ t$ wird eine Wache aufgestellt, falls das Literal den Wert wahr annimmt, ansonsten erhält Punkt $ f$ die Wache.

Abbildung A.4: Das Literalmuster: Der Punkt $ p$ ist nur von den Punkten $ t$ und $ f$ aus sichtbar.
\scalebox{.4}{\includegraphics{pictures/literal}}



Andreas Nüchter
2002-07-10