Some problems become simple when we look at them in the right way. This month, we will consider a geometric problem about points and lines in the plane that arises in computer graphics. Though it initially appears that the quantity we need to determine cannot be practically computed, we'll use duality, a principle that interchanges the role of points and lines, to find an exceptionally elegant solution.
Let's begin with a motivating problem.
Getting rid of the jaggies
The image you see now on your computer screen is displayed by illuminating the screen's pixels, small rectangular regions that are filled with a single color. For instance, here's a digital photograph:
If we zoom in on a region of the photograph, we see individual pixels.
All computer generated images are created this way. For instance, the pixels in the original Toy Story movie, when projected in theaters, were 1/4" on a side. The real trick is to determine how to fill the pixels to most effectively fool our eyes into thinking we are looking at a continuous image.
One simple technique is called antialiasing. Imagine we would like to draw this line across the computer screen.
A standard algorithm for producing lines, called Bresenham's algorithm, tells us to fill these pixels in.
Unfortunately, our eyes easily detect the irregularities, frequently called "jaggies," in the depiction of the line. One way to get rid of the jaggies is a technique known as "antialiasing." When we draw a line, we are really filling in a two-dimensional region:
To help smooth out the jaggies, we will partially shade pixels according to how much they overlap the line. For instance, if the line overlaps a pixel by 75%, we will fill that pixel with a color 75% of the way between white and blue.
When viewed at a proper scale, the difference is seen in the lines below:
A similar issue appears when we draw three-dimensional objects like this.
Such images are frequently drawn using a technique called ray tracing. Here we imagine we are looking at a scene behind the computer screen, and we pass a ray from our eye through the center of each pixel. The pixel is filled with the color of the object in the image that is struck by this ray.
This is a good start, but the color of a filled pixel depends only on the color of the object where the ray strikes it. We are inferring information about the entire pixel based upon what happens at a single point of the pixel. To get around this, we will pass a number of rays through each pixel. Each ray will produce a color given by the object that it strikes. We can then fill the pixel with a color blended from the colors of each ray.
When we choose the points within a pixel to pass rays, some care is required. Our first instinct may be to choose a regular array of points.
Evolution, however, has trained our eyes to look for regularities in an image, which is why we think a particular cloud looks like Snoopy. With a regular array of points, our eyes will still detect jaggies, just on a smaller scale.
To fool our eyes, it is more effective to choose a collection of points randomly. Of course, there are many collections of randomly chosen points, and some will be better than others. For example, this set of randomly chosen points on the left does not seem like a good choice since points appear to be grouped on the pixel's right side. The set of points on the right would seem to be better choice.
We clearly need some way to assess the quality of a set of randomly chosen points. To this end, we will introduce the discrepancy of a set of points, a measure of how good these points will be for our purposes. The aim of this article is to describe what the discrepancy is and how to compute it efficiently.
The discrepancy of a set of points
Let's quickly review the problem we are considering. We are creating a three-dimensional image using a set of pixels so we need to determine the color used to fill each pixel. We will choose a set of points inside each pixel randomly and shoot a ray from our eye through each of these points. The color used to fill the pixel is obtained by blending the colors of the objects that these rays strike.
Since our pixels are small, we will assume that the edge of any object, as seen inside a pixel, appears as a straight line and that the object appears as a half-plane.
Suppose now that we have a set of points $S$ inside the pixel and that $H$ is a half-plane that fills 65% of the area of the pixel. Ideally, the fraction of the points in $S$ that are contained in this half-plane is also 65%. Since we do not know the half-planes that will appear in our pixel, we would like this to be true for every half-plane $H$. This observation motivates the definition of the discrepancy.
Let's denote the pixel by $P$ and assume that it has area one. Given any half-plane $H$, we would like for the area of $H\cap P$ to be the same as the fraction of points in S that are also in $H$. We therefore define the half-plane discrepancy of $S$ with respect to $H$, $\Delta_S(H)$, to be the difference between these two quantities: $$ \Delta_S(H) = \left|\mbox{Area}(H\cap P) - \frac{\#(S\cap H)}{\#S} \right|. $$
The discrepany of $S$ will measure the worst case so we define it to be the supremum taken over all half-planes: $$ \Delta_S = \sup_{H} \Delta_S(H). $$
This looks like a difficult quantity to compute; there are infinitely many half-planes and we need to find the ones that maximize $\Delta_S(H)$. Our goal is to find a means to compute $\Delta_S$ efficiently. To be specific, we will let $n$ denote the number of points in $S$ and keep track of how much effort is required to compute $\Delta_S$ in terms of $n$.
This problem is similar to one in calculus where we wish to find the maximum value of a differentiable function over some interval.
The maximum value will be found among the finite number of local maxima, which may be found using the function's derivative. In a similar spirit, we will compute the discrepancy $\Delta_S$ by first finding the local maxima for $\Delta_S(H)$.
Suppose that $H$ is a local maximum for $\Delta_S(H)$. This means that if we perturb $H$ by a small amount to obtain $H'$, then $\Delta_S(H') \leq \Delta_S(H)$. In other words, $\Delta_S(H)$ cannot increase by perturbing $H$.
This leads to the following crucial observation:
If $H$ is a local maximum for the function $\Delta_S(H)$, then the boundary of $H$ must contain one of the points of $S$.
To see this, consider a half-plane $H$ whose boundary does not contain one of the points of $S$. We may perturb $H$ to a new half-plane $H'$ so that $\#(S\cap H') = \#(S\cap H)$ but $\mbox{Area}(H'\cap P) \neq \mbox{Area}(H\cap P)$.
In this way, we may find a nearby half-plane $H'$ so that $\Delta_S(H') > \Delta_S(H)$.
Now we know that the local maxima for $\Delta_S(H)$ will be found among those half-planes with boundaries that contains points of $S$ so we may divide our search into two cases.
-
The first case is where the boundary of a half-plane $H$ contains exactly one point $p$ of $S$.
Let $U$ be the half-plane above the horizontal line passing through $p$ and let $\phi$ be the angle that $U$ is rotated to obtain $H$. It is relatively simple to write an expression for $\mbox{Area}(H\cap P)$ as a function of $\phi$ and to find its extrema using standard techniques from calculus.
In this way, it is easily seen that the number of local maxima for $\Delta_S(H)$ that pass through $p$ alone is less than twelve.
We therefore find that the number of local maxima for $\Delta_S(H)$ passing through a single point of $S$ is proportional to $n$, the number of points in $S$. To compute $\Delta_S(H)$ for each local maxima, we need to also find $\#(S\cap H)$, which requires us to examine each of the $n$ points in $S$. Therefore we find:
The total amount of work required to examine all the local maxima passing through exactly one point of $S$ is proportional to $n^2$.
-
The second case is where the boundary of a local maximum $H$ passes through two or more points of $S$.
The problem is that there are lots of these: since there are $n(n-1)/2$ distinct pairs of points, the number of these local maxima will be roughly proportional to $n^2$. The amount of effort required to evaluate $\Delta_S(H)$ is proportional to $n$, which means that amount of effort required to examine each one of these local maxima is proportional to $n^3$. This is unacceptably high; for instance, if $n=100$, we will need to perform roughly one million steps to examine all of the local maxima. Here's where we will change our perspective so that we may compute the discrepancies more efficiently.
Duality
As it stands now, we have $n$ points $S$ that we've chosen at random. We would like to consider all half-planes $H$ whose boundary contains at least two points of $S$ and compute $\Delta_S(H)$. There may be half-planes whose boundary contains more than two points, but this will not be typical if our points are chosen at random.
There are roughly $n^2$ such half-planes, and we need to evaluate $\#(S \cap H)$ for each such half-plane. We therefore expect the amount of effort required to compute $\Delta_S(H)$ for all such half-planes to be proportional to $n^3$. We will see, however, that we may compute the half-plane discrepancies with an amount of effort proportional to $n^2$.
The trick is to look at the plane through a different lens. Given points and lines in the plane, which we will call the primary plane, we will define new points and lines in a different plane, known as the dual plane.
To be specific, to a point $p=(p_x, p_y)$ in the plane, we will associate the dual line $p^*$ in the dual plane given by the equation $y=p_x\cdot x-p_y$.
 |
 |
|
Primary plane |
Dual plane |
Similarly, to a line $l$ in the plane defined by the equation $y=mx+b$, we will associate the dual point in the dual plane $p^*=(m,-b)$.
 |
 |
|
Primary plane |
Dual plane |
It is easy to verify that $(p^*)^* = p$; that is, the dual of the dual of $p$ is the point $p$ itself. Also, $(l^*)^* = l$.
You may notice that we have not defined the dual of a vertical line, but this will not be an issue for us.
This association has two important properties:
-
A point $p$ lies on a line $l$ in the primary plane if and only if $l^*$ lies on $p^*$ in the dual plane.
 |
 |
|
Primary plane |
Dual plane |
To see this, notice that the equation defining the first condition is $p_y = mp_x + b$ while the equation defining the second is $-b = p_xm - p_y$. These are clearly equivalent.
Notice that this property implies that if a line $l$ contains two points $p_1$ and $p_2$, then the point $l^*$ is the intersection of $p_1^*$ and $p_2^*$.
-
A point $p$ lies above a line $l$ if and only if $l^*$ lies above $p^*$.
As before, the first condition is defined by is $p_y > mp_x + b$ while the second is defined by $-b > p_xm - p_y$.
 |
 |
|
Primary plane |
Dual plane |
Arrangements
Let's apply this to our computation of discrepancies. We have $n$ points in $S$; when we dualize, we have $n$ lines $S^*$.
 |
 |
|
Primary plane |
Dual plane |
We are also interested in $L$, the set of lines that contain two or more points of $S$. Due to the property above, we know that the intersection points of the lines in $S^*$ are $L^*$.
 |
 |
|
Primary plane |
Dual plane |
A set of lines in the plane is called an arrangement, and the combinatorial properties of arrangements have been much studied by mathematicians. Notice that the lines divide the plane into sets of vertices, edges, and faces. It is straightforward to show that the number of vertices is roughly proportional to $n^2$ as is the number of edges and faces.
Arrangements arise in many applications to computer graphics, such as the motivating problem we are considering here, and there are well known data structures for representing the combinatorial structure of an arrangement as well as algorithms for constructing them. The effort required to do so is proportional to $n^2$.
Let's see now how an arrangement helps us to compute the half-plane discrepancies of $S$. We begin with a line in the arrangement, which we will denote by $p^*$ since it the dual of a point in $S$, and the leftmost intersection point $l^*$ on $p^*$. We compute the number of lines in $S^*$ that lie above, that pass through, and that lie below $l^*$ by considering each of the other lines in the arrangement. The amount of work here is proportional to $n$.
We now walk right along $p^*$ to the next vertex $l'^*$. Here, $p^*$ is intersected by another line $p'^*$ in the arrangement, and we assume, for simplicity, that these are the only two lines in the arrangement that pass through $l'^*$.
By comparing the slope of $p^*$ to $p'^*$, we can easily determine the change in the number of lines above $l'^*$ and the number below $l'^*$. For instance, in the arrangement below, we compute the number of lines above $l^*$. When we move to the next vertex $l'^*$, we see that this number will change by 1.
In this way, we can walk along the entire line $p^*$ and record the number of lines above each of the vertices on $p^*$. The amount of effort to do this is only proportional to the number of vertices on $p^*$, which is proportional to $n$.
This means that the amount of effort required to compute the half-plane discrepancies at the vertices $l^*$ along a line $p^*$ is proportional to $n$. Since there are $n$ lines in the arrangement, computing all the half-plane discrepancies is proportional to $n^2$.
To summarize, it naively appears that the amount of work required to compute the necessary half-plane discrepancies is proportional to $n^3$, which is prohibitively high, but we have found a method, using the dual arrangement, to reduce the amount of work to $n^2$.
To understand what a powerful tool duality gives us, you may wish to sort out what this technique is actually doing in the primary plane containing the randomly chosen points $S$.
Ham sandwich cuts
This technique is useful for solving a wide variety of computational problems. Let's end by considering one more.
A somewhat surprising theorem states that any ham and cheese sandwich may be cut by a plane so that each half sandwich contains the same amount of ham, cheese, and bread. This theorem is particularly useful for parents with young kids.
To illustrate, we'll consider a simpler situation where we have two sets $B$ and $C$ of $n$ points, which we may think of as bread and cheese. This example also makes the unneccessary, but simplifying, assumption that $B$ and $C$ are on opposite sides of the vertical axis and that $n$ is odd.
We would like to draw a line so that half of points of $B$ are on one side as are half the points of $C$.
To begin, let's dualize the points of $B$ and the points of $C$.
In the dual plane, the median level of $B^*$ is a set of edges in the arrangement defined by $B^*$; an edge is in the median level if $(n-1)/2$ of the lines of $B^*$ lie above that edge.
Due to our assumption that all of the points of $B$ lie to the left of the vertical axis, the slopes of the lines in $B^*$ are all negative. This means that the median level moves down as we move to the right.
Likewise, we consider the median level of $C^*$. Here the median level moves up as we move to the right.
Therefore, the median levels of $B^*$ and $C^*$ intersect at a unique point
and this point is the dual of the unique line giving the ham sandwich cut.
Summary
This article describes two applications of duality though its uses are many and varied. Besides fitting neatly in every computational geometer's bag of tricks, duality is a fundamental tool in the study of projective geometry: to every theorem about objects in the primary plane, there is an associated theorem about objects in the dual plane.
The kind of change in perspective that results from applying duality to a particular situation usually delights mathematicians. In writing this column, I hope that I've been able to give a sense of that delight.
References
-
M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry, Springer, 2000.
This fine book discusses the method of ray tracing and supersampling and includes computational details about how to represent arrangements.
-
Joseph O'Rourke, Computational Geometry in C, Cambridge University Press, 1994.
The discussion of the ham sandwich theorem was taken from O'Rourke's book. He includes a few other applications of arrangements and duality as well.
-
Dan Pedoe, Notes on the History of Geometrical Ideas II. The Principle of Duality, Mathematics Magazine, Vol. 48, No. 5 (Nov 1975), pp. 274-277.
Pedoe's paper describes duality as more of a mathematical tool and gives some insight into the mathematical culture into which it was introduced.
David Austin 
