Computer Science – Computational Geometry
Scientific paper
2009-07-07
Computer Science
Computational Geometry
26 pages, 24 figures
Scientific paper
A set $G$ of points on a 1.5-dimensional terrain, also known as an $x$-monotone polygonal chain, is said to guard the terrain if any point on the terrain is 'seen' by a point in $G$. Two points on the terrain see each other if and only if the line segment between them is never strictly below the terrain. The minimum terrain guarding problem asks for a minimum guarding set for the given input terrain. We prove that the decision version of this problem is NP-hard. This solves a significant open problem and complements recent positive approximability results for the optimization problem. Our proof uses a reduction from PLANAR 3-SAT. We build gadgets capable of 'mirroring' a consistent variable assignment back and forth across a main valley. The structural simplicity of 1.5-dimensional terrains makes it difficult to build general clause gadgets that do not destroy this assignment when they are evaluated. However, we exploit the structure in instances of PLANAR 3-SAT to find very specific operations involving only 'adjacent' variables. For these restricted operations we can construct gadgets that allow a full reduction to work.
King James
Krohn Erik
No associations
LandOfFree
The Complexity of Guarding Terrains does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Complexity of Guarding Terrains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Guarding Terrains will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-356579