The Assignment
(Just one part this
time.)
(Please do not consult outside sources,
except your notes and text...)1. Suppose P is a y-monotone polygon; that is, a polygon whose edges consist of two chains which are monotone in the y-direction. Two such polygons are shown below, with the chains colored red and blue in each case.
Devise a linear-time algorithm for triangulating such a polygon.
2. Prove that the complexity of the trapezoidation of a plane polygon with n vertices is linear in n. (The complexity is the total size of the data structure holding the trapezoidation, including vertices, edges and faces.)
3. Suppose you are given a plane polygon with n vertices, together with its trapezoidation, and two points P and Q which lie outside the polygon. Describe an algorithm for determining all the trapezoids which the segment PQ intersects. (See the figure below.) What is the running time of your algorithm? (You should try to devise as optimal an algorithm as possible.)
First check each trapezoid in the trapezoidation. If a trapezoid contains two vertices from different sides of the polygon, connect them with a diagonal.
This decomposes the polygon into (probably) smaller polygons, some of which may be triangles, and the rest of which have a special format. Show that each of the remaining polygons can be triangulated in time proportional to their sizes, and that this implies that the original polygon can be triangulated in linear time.
4. Let's compute a minimum weight spanning tree for n>1 points in the plane using a randomized algorithm. The input is the set of n points, and the outputis a set of n-1 line segments. Given n points in the plane:
a. If there are just two points, output the line segment between them.
b. Otherwise, select one of the points at random, delete it, recursively find the minimum weight spanning tree, add the point back and fix the spanning tree. Fixing the spanning tree consists of connecting the replaced point to its nearest neighbor in the existing spanning tree, and then deleting some edges and replacing them with others.
You should address the following questions:
--What data structure should you maintain in order to quickly find the nearest neighbor? How much time is required, on average, to update this data structure each time a point is added?
--Which edges need to be deleted at each step, and which edges need to be added back?
--How long does it take to find these edges, in terms of the number of edges deleted and added?
--What is the average complexity at each step?
--What is the average total complexity?
Big hint: We mentioned the MWST problem already when we saw some applications of the Delaunay triangulation. We also saw how to generate the DT with a randomized algorithm in time O(n log n).
Some Definitions
Trapezaoidation of a polygon
Given a polygon in the plane, a trapezoidation of that polygon is obtained by extending from each vertex of the polygon horizontal rays in each direction, until they exit the polygon. An example is shown below, where the red, dotted lines are the rays added to the bold polygon.
Spanning Tree
Given a set of points in the plane, a spanning tree on those points is a set of line segments between some pairs of those points resulting in a network having a connection between every pair of points in the set. The weight of this spanning tree is the sum of the lengths of the line segments.
Minimum Weight Spanning Tree
Given a set of points in the plane, the minimum weight spanning tree is the spanning tree which has the smallest possible weight among all spanning trees on that set.
Some Questions
Q: Did you know there were two problems 3?
A: Sigh...
Q: What is meant by "diagonalization" in the first problem 3?
A: That's another word for "triangulation," which is what I meant. I changed the word in the problem now.