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.
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.
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 n2 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.
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(n2)) = 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.
Solution: Starting by grouping the set S of lines in a random fashion in floor( n1/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( n1/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(n1/2
) arrangements and each query runs in time O(log(n)) for
each point, we have checked answered the question in time n*O(n1/2
)*O(log(n)) = O(n3/2 log(n)). This is
O(n3/2+a) for any a >0.