6.838: Geometric ComputingSpring 2005Problem Set 1Due: Thursday, February 24Mandatory PartProblem 1. WidthLet P be a set of n points in the plane. The width of P is defined asminr of unit lengthmaxp∈Pr · p − minp∈Pr · pThat is, it is equal to the minimum, over all projections of P into a line, of a diameter of theprojected set. Yet another interpretation is: squeeze P between two parallel lines; the smallestachievable inter-line distance is precisely the width of P .Give an O(n log n)-time algorithm that computes the width of P .Problem 2. Vertical segment intersectionGiven n vertical-only segments, report all pairs of intersecting segments. For full credit, youralgorithm should run in time O(P + n log n), where P is the number of such pairs.Problem 3. Textbook, exercise 3.3, p. 60A rectilinear polygon is a simple polygon in which all edges are either horizontal or vertical. Givean example showing that bn/4c cameras are sometimes necessary to guard a rectilinear polygonwith n vertices.Problem 4. Textbook, exercise 4.15, p. 93A simple polygon P is called star-shaped if it containts a point q such that for any q ∈ P , theline segment p − q is contain in P . In other words, p “sees” all points in P , without crossing theboundaries.Give a (randomized) algorithm to decide whether a simple polygon P is star-shaped. Youralgorithm should have expected running time O(n). You can assume P is given by a list of verticesin a clock-wise order.1Optional Theoretical PartLet S be a set of disks in the plane. The boundaries of the disks are disjoint, but it is possiblethat one disk D lies entirely inside of another disk D0. In this case, we say that D0dominates D.Give an efficient algorithm which reports the set of all disks which are not dominated by anyother disk.Optional Programming PartImplement a Java applet that constructs a convex hull of a set of (moving) points in the plane.Specifically, the input to your applet is a set S of segments (p1, q1), . . . , (pn, qn), as well as numberof steps k ≥ 1 (a segment is represented by a pair of its endpoints). The applet should do thefollowing, for each i = 0 . . . k:• Compute and draw the set of points Si, which contains all points si=ikp +k−ikq for s =(p, q) ∈ S• Compute and draw the convex hull CH of SiIn addition: we say that s participates in a change in step i, if siis a vertex on the boundaryof CH(Si) but not on the boundary of CH(Si−1), or vice versa. Your applet should compute thetotal number of changes per each step i.Naturally, the applet must also provide a way for the user to specify the input. Graphicalspecification of the segments (by clicking on the endpoints) is strongly preferred.Feel free to add any additional bells and
View Full Document