Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph Theory problems

  1. Feb 7, 2006 #1
    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.
  2. jcsd
  3. Feb 7, 2006 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I would need some definitions before I could help. :frown:
  4. Feb 7, 2006 #3
    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
  5. Feb 7, 2006 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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!)
  6. Feb 7, 2006 #5
    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
  7. Feb 7, 2006 #6
    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 thats 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 gonna assume that guard network alters the definiton of visiblity to mean something like 180? is this true? plz clarify
  8. Feb 8, 2006 #7


    User Avatar
    Science Advisor
    Homework Helper

    Label the corners of the building c1 through cn, such that the first guard sees the corners c1 through ck. For the whole building to be guarded, the second guard must see corners ck through c1 (i.e. ck, ck+1, ..., cn-1, cn, c1). Suppose the guards are at some points p1 and p2.

    Now consider the line L passing through p1 and c1. 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 p2 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 c1 with ck. But without loss of generality, we can just say that the former must be the case, i.e. p2 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 c1 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 c1 (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
    P is guarded
    P is guarded by k guards
    Guards can see one another
    Clear Visibility
    Guard Network
  9. Feb 8, 2006 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
  10. Feb 8, 2006 #9
    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
    Last edited: Feb 8, 2006
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook