Graph Theory Problems: Polygonal Guarding in Simple Polygons with g(P) = 2 and 3

[JasonJo]

These questions deal with polygonal guarding:

a) Suppose P is a simple polygon where g(P) = 2. Prove or disprove that P can always be guarded by two guards that can always see one another (ie the definition of visibility, but not clear visibility)

To disprove all is needed is a counterexample, to prove, a short justification to convince the reader of the truth of the claim is needed, not necessarily a formal proof.

b) Again suppose P is a simple polygon with g(P) = 2. Prove or disprove that P always has a guard network of at most 3.

c) Now suppose that P is a simple polygon with g(P) = 3. Prove or disprove that P always has a guard network of at most 4.

 

[Hurkyl]

I would need some definitions before I could help.

 

[JasonJo]

Our goal in placing guards in a simple polygon P is to make sure that the guards can communicate with each other by means of line of sight. We say that a set of k guards that sees all of P has this property of visibility forms a guard network of size k of the polygon P.

g(P) is the guard number

that's all i have

 

[Hurkyl]

The "guard number" is the minimum number of guards needed so that every point in the polygon can be seen by at least one guard?

For a "guard network", do you require any pair of guards have line of sight (LOS), or merely that there is a chain of LOS from one guard to another, through some intermediate guards?


Well, what have you tried on these problems?

(The first thing I've done is simply to try and find a polygon with g(P) = 2!)

 

[JasonJo]

i tried finding polygon's P such that:

1) the g(P) = 2
2) and the two guards cannot see each other

and I've tried various polygons and all of them seem to be able to see each other.

HOWEVER, i can't prove that they always can.

i tried reasoning along these lines:
if two guards sufficiently see all of the polygon P, but aren't visible to each other, then there exists some region or some infinitesimal line segment that is not seen by either guards, contradicting that two guards sufficiently see all of P.

i dunno, I'm scared lol

 

[neurocomp2003]

you might want to add Computational Geometry to the title..though it is a bit of both...Sorry can't really help you any further my comp.geometry is a bit rusty(though i aced the course i took)

"simple polygon" = convex polygon right?
"visiblity" =is there a degree angle of visibility or do we assume 180 or 360?
i can't remember the definition of visiblity

if the def'n of visiblity that you have is the same as the one i have in O'rourke then its defined as 360. And the definition of visiblity between two points is that the ENTIRE line connecting them also belongs to the polygon.\

Thus part (A) waht you are showing is whether there are two points
in the polygon, such that the line connecting them is not a subset of the polygon and the union of the visiblity range = P...This is rather easy if your polygon is convex which i hope that's what a simple polygon means. If it is...start with two vertices and the notion of simple polygons to show that each vertices is visibilty to those two vertices. Also refer to the idea of ear clipping in computaitonal geometry. It might give you a better sense of how to prove the problem.

never heard of the term guard network before, and I'm still confused as to your definition of guard networks...because if g(p) =2 then by your definition guard network=2 should also be true...BUT I'm going to assume that guard network alters the definiton of visiblity to mean something like 180? is this true? please clarify

 

[AKG]

Label the corners of the building c₁ through c_n, such that the first guard sees the corners c₁ through c_k. For the whole building to be guarded, the second guard must see corners c_k through c₁ (i.e. c_k, c_k+1, ..., c_n-1, c_n, c₁). Suppose the guards are at some points p₁ and p₂.

Now consider the line L passing through p₁ and c₁. Then this line splits R² into two parts, one containing the polygon, and one not. For the guard to see each other, we require that p₂ either lies on L, or on the side of L that doesn't contain the polygon. Well, actually, either the above is the case, or something similar to the above is the case. That "something similar" comes from replacing c₁ with c_k. But without loss of generality, we can just say that the former must be the case, i.e. p₂ is either on L, or on the side of L not containing P.

Now it's easy to see that a guarding is always possible. Start by picking a line through c₁ that is not parallel to any of the sides of P. This is possible as there are only finitely many sides, but uncountably many lines passing through c<sub>1 (that coincide with P only at c1). Without loss of generality, suppose L is horizontal, and P is above L (we could just rotate space to get things this way without changing the problem). Now there is a corner c of P, somewhere on the other side of P from c1 where the edge of P extending leftwards from c has positive slope spos, and the edge of P extending righwards from c has negative slope sneg. Place p2 on L sufficiently far to the right so that the slope of the line through c and p2 is greater than sneg, and place p1 on L sufficiently far to the left os that the slope of the line through c and 1 is less than spos. In fact, it is possible to do this moving L down a very small amount, and then moving the gaurds farther out if necessary. Doing this, the guards will have clear sight of one another (whereas previously, they had the corner c1 partially blocking their way).

What's a guard network? Also, does the above solve your problem, since it's not entirely clear what the problem even is, you haven't defined many things:

Simple Polygon
g(P)
P is guarded
P is guarded by k guards
Guards can see one another
Visibility
Clear Visibility
Guard Network</sub>

 

[matt grime]

It can't be convex that is meant by simple since that ought to mean 'only one guard' in whatever sense is meant.

The standard (counter) examples to the guard are the so-called combs, I leave it to you to guess what these might be.

 

[JasonJo]

Chvataal's comb can be guarded by 2 guards who have a line of sight

i got them figured out, thanks for everyone's input