Other Problems Using Duality

Median Slope Selection

Given a set of n points in a plane we want to compute the median slope of the lines that connect each pair of points. This is a problem that has been looked at very closely over the past fifteen years. An optimal algorithm was first found by Cole et al. in 1989 that ran in O(n logn), and an optimal randomized algorithm was first proposed by Jiri Matousek in 1991, but generally we talk about algorithms that run in O(n2).

With n points the number of lines that were are looking through are to the order of O(n2). Mapping all these lines to the dual will now simplify the problem, because the x-coordinate of the dual plane correspond to the slope of the lines in the primal. All we must now find is the median x-coordinate of our points, that point will correspond to the line with median slop in the primal. Computing the median can be done in linear time in the size of the data, which in this case in O(n2).

Ham Sandwhich Cuts

Ham Sandwhich cuts are a classic problem in Computational Geometry. Here given 2 sets of points, find a line that bisects both the sets of lines. I'm not going to cover specifics since this is a topic of another project entirely, but one should be made aware that duality is used in solutions for this problem.