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

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 + 2*ceiling(*k/2*). This equals *3 k = n, *
if *n * is even, and * 3k + 1 = n + 1, *
if *n * is odd.

Given a set

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

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 ^{2} *points to one of a convex hull
of only

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 2*n* 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

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^{2})) = *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

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.*