Radial Vertex Selection

Another problem that uses duality is Radial Vert Selection. Say we have a set of lines L ={l₁,...,l_n} in general position in R² with a vertex set V(L) that is defined as all points where lines of set L intersect, so it's all intersection points of L. Given a point P in R² we order the vertices according to the slope of the lines that join P to the points in V(L). We then want to select the k^th in the ordering.

The Solution

In the solution to such a problem we'll need to apply duality twice and a rotation! So let's look at how we get a solution, then see the steps played out on the Java applet.

Step 1: First map the set of lines L and our point P to the dual plane. As a result we have a set of points S and a line h.

Step 2: We will now rotate the dual plane to make the line h vertical.

Step 3: We now once again apply a dual transformation on the rotated dual plane.

Step 4: We now have a set of lines agaion and the dual of the rotated line h is at infinity. So now we now must rotate this plane so that this point is at vertical infinity.

Step 5: It is now easily shown that this problem is now the usual vertex selection in the new plane. This has been shown by Cole et al. to take O(nlogn) time.

Now let's look at an applet that goes through the steps of this algorithm. First pic of point on the plane, this will be the point P. Then click on Generate, this will generate the lines that will determine the intersections. Then click on Transform to map the lines and point P to the dual. Rotate will then rotate the plane till the line P^* is vertical. Then clicking on Vert. selection will map the points and line back to the primal. Unfortunately doing the last step of the algorithm is not easy to visualize, but the black dots represent the new position of the intersections and the red dots the old.