Assignment 1
This assignment has 2 parts. Everyone should complete the first part,
and then select one of the two options for the second part.
Part I --- Exercises
1. How many guards are needed to guard the art galleries shown below:
2. How do those numbers compare with Chvatal's n/3 bound?
3. Fisk's proof (of Chvatal's n/3 theorem) used a 3-coloring of a
triangulation of the art gallery to obtain n/3 guards. In this proof,
we selected our guards to be on that set of vertices which
represented the color that appeared least frequently. In each of the
art galleries shown in problem 1, is there a triangulation and
coloring thereof which yields the number of guards actually needed
for those art galleries?
4. Call a polygon "Fiskly" if its optimal number of guards can be
obtained by some coloring of some triangulation of that polygon, as
suggested in prolem 3.
a. Prove that all convex polygons are Fiskly.
b. Prove that all pentagons are fiskly. (Hint: This can be done
without actually drawing any pentagons, though you may
draw as many as you wish.)
c. Find a hexagon that isn't Fiskly. You should show your
polygon, nicely drawn, and prove rigorously that it isn't Fiskly.
5. Prove that for every subset S of the plane, S is a subset of cl(S). Can a
finite subset of the plane with at least one point be open?
6. Prove that every finite set of at least 3 points, not all on a line, contains an empty triangle, that is, a triangle which contains no other points of the set within it.
7. Give an example of a set in the plane whose boundary is a single point.
8. Express (5, 5) as a convex combination of (1, 2), (3, 30) and (100, 2)
9. What is the boundary of a line segment in the plane?
10. An edge of a polygon is called extreme if the polygon lies entirely to one
side of the line containing that edge. Does every polygon have an extreme
edge? Prove your answer. (Note: An extreme edge can contain only two
vertices of the polygon; namely, those incident with the extreme edge.)
Part II --- Problems and Programs
Select one of the following tracks:
Theory
(Please do not consult outside sources...)
11. Suppose you are given an art gallery with n orthogonal walls (that is, walls
which are all parallel to the x- or y-axes. Chvatal's theorem guarantees that
no more than n/3 guards are needed, but perhaps the special shape of this
gallery means that we can get away with fewer guards. In fact, n/4 guards
are always sufficient.
a. Devise a worst-case polygon to show that fewer guards do not suffice,
for all values of n.
b. Must an orthogonal polygon always have four consecutive vertices a, b,
c, and d on the boundary so that the quadrilateral has no other vertices
of the polygon in its closure?
12. A vertex of a polygon is called lonely if the only other vertices of the
polygon which it can see are those two which are adjacent to it along the
boundary of the polygon.
a. Show that if u, v and w are consecutive boundary vertices of a polygon,
and v is lonely, then any triangulation of the polygon must contain the
diagonal uw.
b. Suppose a polygon has an extreme edge (as described in problem 10)
where u and v are the vertices on that edge. Show that it is possible to
modify the polygon by deleting edge uv, adding a new vertex x and adding
edges ux and vx, so that the resulting figure is still a polygon, still has an
extreme edge, and vertex x is lonely.
c. Prove that for all n >= 3, there exists a polygon with n sides which has
exactly one triangulation.
13. Prove that a triangulation of a polygon with n sides must employ n - 3
diagonals, and consist of n - 2 triangles.
14. Let T be a triangulation of a polygon and edge uv be one edge of the
polygon. Suppose we wish to use red, white and blue to color the vertices
of T, and that u and v have already been assigned colors. Show that there
is exactly one way to finish the coloring of the triangulation.
Implementation
This program takes as input a file of points in the form
(1, 3)
(2, 4)
(22, 99)
end
where each point is on a new line, and the last line contains "end" You may
assume that all points have integer coordinates.
Your program should:
11. Read the input file, and output the point or points which have the least
x-coordinate.
12. Output all triples of points which are colinear, or say that there are none.
13. Output a triangulation of the polygon formed by considering the input
points as being given in order around the boundary of the polygon. (You may
assume that the input file described a simple polygon.) The triangulation should
be indicated by listing which diagonals you added. For example;
diagonal (1, 2) - (3, 4)
diagonal (1, 2) - (54, 7)
...
14. Finally, output the number of points of the set which lie interior to the
triangle formed by the first three points in the input file.
Some Definitions
Polygon
Simple, closed curve in the plane which is the union of line segments.
Simple
Non self-intersecting
Seeing
Two points in a planar set S are said to see each other if the line segment between them lies entirely inside the set S
Convex
A set is called convex if every pair of points in that set can see each other
Closed
Bounds a region of the plane, separating the plane into two parts, and "inside" and an "outside."
Interior Point
Given a set S in the plane, an interior poin of that set is a point p in the set such that there exists some positive (but possibly very small) radius r and a disk of that radius centered at p which lies entirely in the set.
Interior
The interior of a set S is the set of its interior points, and is denoted int(S)
Open and Closed
A set is called open if it is equal to its interior. A set is called closed if it is the complement of an open set.
Disk
A disk of radius r, centered at p = (x, y) is the set of points
{(x, y) | x2 + y2 <= r}
Limit Point
Given a set S in the plane, p is a limit point of S if there exists some infinite sequence of (not necessarily distinct) points from S, p1, p2, ... so that the limit of the distances between pi and p, as i goes to infinity, is 0.
Closure
The closure of a set S in the plane is the set of all limit points of S, and is denoted cl(S)
Boundary
The boundary of a set S in the plane is the closure of S minus the interior of S, and is denoted
.Some Questions
4c. By fiskly do we mean only polygons that require one guard by some triangulation and 3-coloring or do we mean polygons that require n/3 floor guards. Because for the hexagon we know that that we can draw one that requires 1 guard and one that requires 2 guards.
"Fiskly" means that if k is the minimal number of guards, then there is some triangulation and coloring with its smallest color class of size k.
6. Are we allowing the case where 3 colinear points can be considered a triangle? Also, you said for a finite number points. If my finite number is 1 or 2 it is not possible to even construct a triangle. Is this a trick question?
Oops... Nope, not a trick question. Just poorly stated. I've edited it now. Thanks!
10. Are we allowing the case where on all edges there can exist extra points? By your definition of an extreme edge there can be no more than 2 vertices on each edge. If on each of my edges I add an extra point is that not the same as adding an extra vertice thus creating a polygon with no extreme edges?
You are right. That's one way to create polygons with no extreme edge. You can further ask: Do there exist polygons with no extreme edges, whose vertices lie in general position, having no three on a line? That's more like what I meant to ask.
(Added
2/11/04)
13. Can we assume that the points are given in counter clockwise order?
Yes, if you want. But it would be cooler to have the program figure that out.