600.488 Homework Assignment 7

Draw a line segment s in the plane, and draw a representation in the dual plane of the set of all lines that intersect s.

Solution: For a point P, the dual of the set of all lines through P is just the set of points in the line dual( P ). Thus the dual of the set of all lines that intersect s is the pencil of all lines between dual( P ) and dual( Q ), where P and Q are the enpoints of s.

Consider a point set S defined as follows. Place three rays emanating out from the origin, each separated from the next by an angle of 120 degrees. Place n/3 points of S to be equally spaced along each ray. How many edges are on the median level of the arrangement formed by the duals to the points in S?

Solution: Without loss of generality, assume one of the rays points upward from the origin. To simplify things, we assume n= 3 k, with k an integer. Then k lines will be horizontal, and the two other groups of parallel lines have slopes of opposing signs.

Approaching this line arrangement from the left (coming from infinity), the k lines with negative slope will lie above all other lines. In vertical order they are then followed by the horizontal lines. Thus the median level is along a horizontal line. In the horizontal group of lines, it will have rank ceiling(k/2) counting from top down.

As we move towards the right, the intersections between each pair of groups will appear in clumps: First we will visit the intersections between horizontal lines and the group of lines of positive slope. Next, we encounter intersections between the two non-horizontal groups. Finally, we meet the intersections between the lines with negative slope and the horizontal lines.

Starting from the edge on the horizontal line that stretches to -infinity we will intersect a line with positive slope. After the intersection (and this will be true in every instance the line we are travelling along is intersected), the vertical ranks of the lines is interchanged, so we must switch lines to remain at the same level. If we continue, the next intersection we shall find is the horizontal line right above the one we started on, which we then move to. As we traverse this arrangement, we will travel along a horizontal edge in each of the r = ceiling(k/2) lines which include the line we started on and those above it, and along positively slanted edges, in the same number r, lying on the first r lines of that group that we meet from the left. We finally leave this group on a slanted edge towards the second group of intersections.

A similar pattern takes place as we arrive at the second group. We will leave this group after finishing the left to right traversal of positively slanted lines, and will move to the third group. We leave this group towards infinity after completing the left to right traversal of negatively sloped lines, on the line same horizontal line we started.

Thus the total number of edges: one for every non-horizontal line + two for every of the r = ceiling(k/2) top horizontal lines = 2 k + 2ceiling(k/2). This equals 3 k = n, if n is even, and 3k + 1 = n + 1, if n is odd.

Given a set S of n lines in the plane, design an O(n log n)-time algorithm for finding the convex hull of the (finite) vertices in the arrangement of the lines in S.

Solution: Order the set of angles A_l, where tan(A_l) = slope of l, for the lines l in S, in a counterclockwise fashion starting with the smallest of these angles, where arctan() is chosen to have image in (-pi/2, pi/2]. Using an efficient sorting algorithm, we accomplish this in O(n log(n)) time.

As the lines in S approach infinity, they assume the configuration above. More explicitly, if C is a circle containing all intersections between any pair of lines in S, then as we traverse C in a counterclockwise fashion we meet the lines of S according to their slopes only. If A_i and A_j are consecutive angles in the ordering above, they define an infinite sector of the plane. The intersection of the lines l_i and l_j may define a point in the convex hull of the arrangement. I claim these are the only possible candidates for vertices in the convex hull. These is because the vertices in the convex hull are visible "from infinity". One way an intersection may be visible from infinity is for it to be the last intersection in each of the lines in which it lies. These implies that these lines are consecutive in C. Moreover, if a certain intersection is visible from infinity, so are all the other intersections that lie between that intersection and infinity, so if it is not the last intersection, it is not a candidate to be on the convex hull.

There are n pairs of angles (do wrap around) and by computing the intersection of each of these pair of lines, we obtain n points, including all possible vertices of the convex hull. Thus in O(n log(n)) time we have reduced the problem of finding a convex hull of n² points to one of a convex hull of only n points, a problem we can solve in O(n log(n)) time.

In fact the set of points we obtain is not arbitrary. It is "almost ordered" in circular fashion. As we traverse the circle along C, the correct order in which a point P should be visited is not completely defined, because if the sector containing P is rotated by pi, it gives another sector which defines P, and it is not clear when P should be visited as we traverse the convex polygon. This may be solved by doubling each line and orienting each copy in opposite directions, strengthening the condition "visible from infinity" to visible "from infinity from a give side" and testing each intersection to decide in which side it lies. Then an extra computation would be necessary to decide, for each intersection of consecutive oriented lines, (there are now 2n pairs) to decid from which side (if any) it would be visible. But if we take this care, the convex hull can be obtained in O(n) time after the step in previous paragraph. Namely, we obtain a single polygon by this process, which can be "relaxed" to a convex polygon if not convex already.

Given a set S of n points in the plane, design an efficient data structure that can answer line-dragging queries, where a line-dragging query is specified by giving a non-vertical line l and asking for the first point of S that would be hit by dragging l vertically upward keeping its slope the same. Shoot for a running time of O(log n) time with a data structure using O(n²) space.

Solution: Dualize the set S and construct the arrangement of the lines in the dual. Dragging the line l corresponds to dragging the dual of l along the ray r that connects it to the origin (used for dualization). Since point location queries run in time O(log(n²)) = O(log(n)), we may locate the cell in which the first intersection with r will take place in the time alloted. Once we know the (convex) cell, computation of intersection of a line and convex polygon can also be done in O(log(n)) time, as we have seen before.

Suppose you are given a set S of n lines in the plane, and a set T of n points in the plane. Design an efficient algorithm to determine if one of the points in T is on one of the lines in S. (Hint: Shoot for an algorithm running in a little more than O(n^3/2) time, which begins by dividing S into O(n^1/2) groups of size O(n^1/2) each.) Characterize as closely as possible with the big-oh notation the asymptotic running time of your algorithm?

Solution: Starting by grouping the set S of lines in a random fashion in floor( n^1/2 ) groups of approximately same number of lines. Some of the groups may contain one line more than others, in case n is not a perfect square; each of these groups may contain up to floor( n^1/2 ) + 2 elements.

For each group, construct the line arrangement. It takes O( n ) time and space to construct. For each point, perform a point query for each arrangement. Since there are O(n^1/2 ) arrangements and each query runs in time O(log(n)) for each point, we have checked answered the question in time n*O(n^1/2 )*O(log(n)) = O(n^3/2 log(n)). This is O(n^3/2+a) for any a >0.