2.2: Apply algorithm FINDINTERSECTIONS from this chapter of the text, but terminate the algorithm as soon as it finds the first intersection.
2.5: All but the third equality are true.
8.2(a): The collection of lines that do not pass through the top or bottom infinite cells of the three-line arrangement dual to p, q, r.
8.2(b): The points on a line that are outside of some line segment.
8.14: Construct the dual line arrangement using algorithm CONSTRUCTARRANGEMENT and look for the vertex with the largest number of incident lines.
3.6: Lemma: any tree with vertex degree at most three has an edgewhich splits the tree into two parts, each of which has at least 1/3 of the vertices of the tree. (Proof idea: if an edge e splits the tree more unevenly, one side of e contains more than 2/3 of the vertices, and one of its two neighboring edges on that side gives a better split. So a split that can not be improved must at least be 1/3-2/3.)So to solve the problem, triangulate the polygon, apply the lemma to the dual tree, and split the polygon on the diagonal dual to the tree-splitting edge.
4.7(a): A square can not be removed by rotation, but can by translation. See below for rest of answer.
4.7(b): Draw a line perpendicular to each edge of the object, through the counterclockwise endpoint of the edge. Form a halfplane bounded by this line, on the other side of the line from the edge. A center of rotation must be inside this halfplane, and a center exists if and only if all these halfplanes have a nonempty intersection. A translation corresponds to a pivot point at infinity, so if the intersection is bounded, as in the drawing below, the object can not be removed by a translation.
4.12(a): By construction, any item is equally likely to be the last item in the permutation, so the probability of generating any particular permutation is 1/n times the probability of generating the permutation of the other n-1 items. But by induction this is 1/(n-1)! so the probability of generating the overall permutation is 1/n! as required.
4.12(b): If n=3, and we change the line, then there are two calls to RANDOM(3) so the probability of any particular sequence of events is 1/9 and the probability of any particular output is a multiple of 1/9. But the desired output probability of each permutation, 1/6, is not a multiple of 1/9.
15.1: Choose a start and goal near the midpoints of opposite edges of a regular n-gon.
5.11: Sweep a vertical line left-right across the line segments, using a sorted list of segment endpoints to keep track of the sweep events. Also keep a binary search tree of the intersections of the sweep line with the horizontal segments, sorted by the y-coordinates of the intersection, and store at each node of the search tree a count of the number of descendants of that node.When the sweep line crosses the left or right endpoint of a horizontal segment, update the augmented binary search tree appropriately. When the sweep line crosses a vertical segment, use the search tree to count the number of horizontal segments it crosses.
6.7: Binary search to find the edge of P crossed by a ray from p in the direction of q. If p is not given you could use linear programming to find it as a preprocessing step.
7.7: No. Whenever any new point is crossed by the sweep line, it creates two new breakpoints, both moving in opposite directions along the same Voronoi edge; unless this edge is parallel to the sweep line, only one of the breakpoints will move downwards.
10.9: Store a range tree of left endpoints of intervals.At each node of the range tree, store the intervals in the canonical subset of the node, in sorted order by their right endpoints. To answer a query, use the range tree to find O(log n) canonical subsets covering the intervals with left endpoints greater than x, and scan each canonical subset's sorted list until reaching a right endpoint greater than x'.
12.10: As the hint says, start the partition by using all vertical lines x=2i where i is an integer and where the line cuts at least one disk. Each disk is cut at most once so the total complexity of all vertical strips after this step is at most 2n. Next, within each strip, cut horizontally by lines y=2i whenever such a line crosses a part of the disk within the strip; this again at most doubles the total complexity. After these two stages,each remaining cell of the partition can contain at most a constant number of disk parts, so if we repeatedly find two parts in the same cell and separate them by a line the complexity will remain linear.
9.8: Let C be the circle circumscribing triangle pipjpk. Form circle Ci by starting with C and continuously shrinking it, keeping the shrunken circle tangent to C at pi, until it crosses q; the resulting Ci is empty and has q and pi on its boundary, so qpi is a Delaunay edge. By a symmetric argument, so are qpj and qpk.
9.17: Form an isosceles triangle with base smaller than its height, and add a fourth point outside the triangle and very close to the midpoint of the base. The Delaunay triangulation will use the diagonal from the fourth point to the apex, the minimum weight triangulation will instead use the isosceles triangle's base.
11.2: Each new point uses at most linear time (due to the upper bound theorem) so the total time is O(n^2). One bad example consists of n/2 points on or near a circle and n/2 points along or near a line perpendicular to the circle through its center. If the points are added on the circle first, and then in increasing order of their distance from the circle, each point along the line will have a visible region boundary with complexity Theta(n) and the total complexity will be Theta(n2).
F1: Two crossing double wedges each contain the apex of the other wedge.
F2: Use the lifting transformation taking each two dimensional point (x,y) to a three dimensional point (x,y,z=x2+y2); a circle in two dimensions separating the red points from the blue points corresponds to a linear function ax+by+cz+d that is negative for the red points and positive for the blue points.The constraint that ax+by+cz+d be positive or negative is linear, so the coefficients a,b,c,d can be solved as a linear programming feasibility problem.
F3(a): Form the arrangement of lines, preprocess it for point location, and locate each input point within the arrangement.
F3(b): Partition the lines arbitrarily into sqrt(m) groups of sqrt(m) lines each, and apply part (a) separately to each group.
F4: The problem is somewhere in the sentence "When we handle a query, we use the segment tree to find O(log n) canonical sets, and we apply the query to the third-level data structure for each set". The query does not have any information to tell us which range of slopes to look at, so there is no obvious way of picking out only O(log n) canonical sets to query.