Aspects of Primal-Dual Transforms


Primal-Dual transforms rely on the simple aspect that points in the xy-plane contain have two pieces of information, the x and y coordinates, and that lines in the plane also have pieces of information, the slope and y-intercept. Hence we will use this information to build a mapping from one plane to another and vice-versa. The planes will be the primal plane and the dual plane. It's important to note that vertical lines will not be defined.

Primal Dual
(a,b) y = ax - b
y = ax + b (a,-b)


One of the properties that Primal-Dual Transforms have is the Above/Below property. This states that the if the point c lies above the line l in the primal then the corresponding point l* lies above the line c*. This property will be exploited later on when we look at algorithms that use duality.

abovebelow.GIF - 2520 Bytes

Incidence Preservation

The second property of Primal-Dual Transforms is the Incidence Preservation property. Where if a line l contains point c in the primal, when they are mapped to the dual the corresponding line c* contains the point l*. Once again we will see the usefullness of this property in the algorithms that are to follow.

Incidence.GIF - 2791 Bytes

This property comes in handy when we look at two lines that intersect in the primal. When these two line are mapped to the dual, the line that is incident with these points is defined by the intersection point in the primal.

Intersection.GIF - 3466 Bytes

Line Segments

When a line segment is mapped from the primal to the dual what is created is a bounded region. To understand this lets first look at what a line segment is, it's a line between two points. Thus the two points are mapped to lines and the line itelf is mapped to the point where the two lines intersect, due to incidence preservation. The region that is bounded represent all the points on the line segment. Because since the x-coordinate determines the slope and the line segement is continuous, it's like taking a line a rotating it.

LineSeg.GIF - 3065 Bytes

Other Types of Duality

Other forms of duality exist and are used in many different ways, which we will not explore in this project, but they are important to acknowledge. A "polar" mapping of duality uses the aspects of the unit circle. All points within the unit circle will map to lines that will not intersect it. While points on the unit circle will produce lines that are tangent to that point, and points outside the circle will map to lines that intersect the circle. The "Polar" mapping goes as follows:

(a,b) maps to ax + by = 1

The second form of duality we will discuss briefly is the "parbola" mapping. This mapping takes all point that are above the parbola to lines that don't intersect the parabola. While points that are below the parabola are mapped to lines that intersect the parabola. The "Parabola" mapping goes as follows:

(a,b) maps to y = 2ax - b