Arrangements and Duality or How I Learned to Slice a Ham and Cheese SandwichThe aim of this article is to describe what the discrepancy of a set of points is and how to compute it efficiently....David Austin
IntroductionSome 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 jaggiesThe 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 twodimensional 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 threedimensional 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 pointsLet's quickly review the problem we are considering. We are creating a threedimensional 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 halfplane.
Suppose now that we have a set of points $S$ inside the pixel and that $H$ is a halfplane that fills 65% of the area of the pixel. Ideally, the fraction of the points in $S$ that are contained in this halfplane is also 65%. Since we do not know the halfplanes that will appear in our pixel, we would like this to be true for every halfplane $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 halfplane $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 halfplane 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 halfplanes: $$ \Delta_S = \sup_{H} \Delta_S(H). $$ This looks like a difficult quantity to compute; there are infinitely many halfplanes 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: To see this, consider a halfplane $H$ whose boundary does not contain one of the points of $S$. We may perturb $H$ to a new halfplane $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 halfplane $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 halfplanes with boundaries that contains points of $S$ so we may divide our search into two cases.
DualityAs it stands now, we have $n$ points $S$ that we've chosen at random. We would like to consider all halfplanes $H$ whose boundary contains at least two points of $S$ and compute $\Delta_S(H)$. There may be halfplanes 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 halfplanes, and we need to evaluate $\#(S \cap H)$ for each such halfplane. We therefore expect the amount of effort required to compute $\Delta_S(H)$ for all such halfplanes to be proportional to $n^3$. We will see, however, that we may compute the halfplane 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 xp_y$.
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)$.
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:
ArrangementsLet's apply this to our computation of discrepancies. We have $n$ points in $S$; when we dualize, we have $n$ lines $S^*$.
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^*$.
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 halfplane 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 halfplane discrepancies at the vertices $l^*$ along a line $p^*$ is proportional to $n$. Since there are $n$ lines in the arrangement, computing all the halfplane discrepancies is proportional to $n^2$. To summarize, it naively appears that the amount of work required to compute the necessary halfplane 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 cutsThis 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 $(n1)/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.
SummaryThis 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
The AMS encourages your comments, and hopes you will join the discussions. We review comments before they're posted, and those that are offensive, abusive, offtopic or promoting a commercial product, person or website will not be posted. Expressing disagreement is fine, but mutual respect is required. David Austin 
Welcome to the These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics. Search Feature Column Feature Column at a glance 
Comments: Email Webmaster 
© Copyright
, American Mathematical Society


