[Math] Is this dual transform incidence and order preserving

Question

I am trying to understand duality explained in the book Computational Geometry Algorithms and Applications, 3rd Ed – de Berg et al. Unfortunately, I have some problem of solving a question in this book. In the book they explain how a point p = ($p_x$ ,$p_y$) can be transformed by a duality transform to $p* := (y= p_x x – p_y)$ .

The duality transform got the following properties:

**Observation 8.3** Let p be a point in the plane and 
let l be a non-vertical line in the plane. The duality transform o → o∗ has the
following properties:

 1. It is incidence preserving: p ∈ l if and only if l∗ ∈ p∗ .
 2. It is order preserving: p lies above l  if and only if l∗ lies above p∗ .

This is the question I am trying to answer:

The dual transform of Section 8.2 has minus signs. Suppose we change
them to plus signs, so the dual of a point ($p_x$ , $p_y$ ) is the
line y = $p_x$ x + $p_y$ ,
and the dual of the line $y = mx + b$ is the point (m, b). Is this dual
transform incidence and order preserving?

The problem is that I don't know how a line would look like if it is defined by $p* := (y= p_x x + p_y)$. I hope that someone could help me solve this question.

Answer 1

The dual transform you propose does not preserve incidence.

Example. Consider the line $\ell$ given by $y = -x + 2$ and the point $p = (1,1)$. Then $p$ and $\ell$ are incident. However we have \begin{align} p^* \: &= \: (y = x + 1);\\[1ex] \ell^* \: &= \: (-1,2). \end{align} These are not incident. This is illustrated in the figure below.

Now it is not surprising that the transform is not order-preserving either. I leave it up to you to find an example.

---

All is not lost, though. Interestingly, there is a plane duality where the point $p = (p_x,p_y)$ is sent to the line $y = p_x\:x + p_y$. However, this duality is not equal to its inverse: to go back from the dual plane to the primal plane, we have to send the dual point $q = (q_x,q_y)$ to the line $y = -q_x\:x + q_y$ in the primal plane. \begin{array}{|ccc|} \hline \text{primal:} & & \text{dual:}\\[2ex] (a,b) & \quad\longleftrightarrow\quad & y = ax + b\\ y = cx + d & \quad\longleftrightarrow\quad & (-c,d)\\ \hline \end{array} This duality does indeed preserve incidence. (I don't know whether it is order preserving; I don't find that particularly interesting. Perhaps you can work it out for yourself if you really want to know.) You can see that it fixes the above example: we reflect the point $\ell^* = (-1,2)$ in the $y$-axis and do indeed obtain a point on the line $p^*$. More generally, it is easily seen that the following are equivalent:

• The point $(a,b)$ lies on the line $y = cx + d$.
• We have $b = ca + d$.
• We have $d = -ac + b$.
• The point $(-c,d)$ lies on the line $y = ax + b$.

Now how did I find this alternative duality? I could have just tried to make the algebra work (and I'm a little embarrassed now that I didn't do that), but instead I tried to gain some geometric intuition for the problem. Both of these dualities are special cases of duality in projective geometry.

A short introduction to projective geometry. Let $\mathcal L$ be the set of all lines in the plane, including the vertical ones. We define an equivalence relation $\sim$ on $\mathcal L$ by saying two lines are equivalent iff they are parallel. Now for each equivalence class $C \subseteq \mathcal L$ we define a new point $p_C$ "at infinity" that is incident with every member of $C$. We furthermore add a new line, called the line at infinity, that is incident with every point at infinity (and no other points). The geometry thus obtained has the following fundamental properties:

• For every pair of points $p,q$ with $p\neq q$ there is a unique line that is incident with both $p$ and $q$.
• For every pair of lines $\ell,m$ with $\ell \neq m$ there is a unique point incident with both $\ell$ and $m$.

Now, this definition is a little imprecise, but there is another construction that yields the same result. Consider the three-dimensional vector space $\mathbb{R}^3$. Let $P$ be the collection of all one-dimensional subspaces of $\mathbb{R}^3$ and let $L$ be the collection of all two-dimensional subspaces of $\mathbb{R}^3$. We define an abstract geometry where $P$ are the points and $L$ are the lines, such that a point $p\in P$ and a line $\ell \in L$ are incident if and only if $p \subseteq \ell$ holds (as subspaces of $\mathbb{R}^3$). One can use linear algebra to show that this geometry also meets the two fundamental properties listed above (and in fact it is the same projective plane as the one described above). This plane is called the real projective plane and is denoted by $\mathbb{P}^2$. I shall use this construction in the remainder of my answer.

Note that in the second construction, there is no special line at infinity. Once we choose an embedding $\varphi$ of the real plane $\mathbb{R}^2$ into the projective plane $\mathbb{P}^2$, the line at infinity is the complement $\mathbb{P}^2 \setminus \varphi[\mathbb{R}^2]$.

The typical way to embed $\mathbb{R}^2$ into $\mathbb{P}^2$ is this: we choose an affine hyperplane $\mathcal A\subseteq \mathbb{R}^3$ that does not contain the origin, which can be identified with the Euclidean plane $\mathbb{R}^2$. Then we associate every point $p$ on $\mathcal A$ with the unique one-dimensional linear subspace of $\mathbb{R}^3$ containing $p$. Similarly, we associate every line $\ell$ on $\mathcal A$ with the unique two-dimensional linear subspace of $\mathbb{R}^3$ that contains $\ell$. This explains the name, projective geometry: the points (one-dimensional subspaces) and lines (two-dimensional subspaces) of $\mathbb{P}^2$ are projected onto the affine hyperplane $\mathcal A$, where they become actual points and lines.

Now, I may choose an identification of the Euclidean plane with a subset of the projective plane $\mathbb{P}^2$. For this I choose to work with the affine hyperplane $\mathcal A = \{(x,y,z) \in \mathbb{R}^3 \: : \: z = -1\}$. This is illustrated in the following example:

Example. Consider (in the Euclidean plane) the point $p = (3,-2)$ and the line $y = x - 2$.

After embedding these into the projective plane, the point corresponds with the one-dimensional subspace $\{(3\lambda,-2\lambda,-\lambda) \: : \: \lambda \in \mathbb{R}\}$, indicated in blue, and the line now corresponds with the two-dimensional linear subspace given by $x - y + 2z = 0$. (After all, filling in $z = -1$ gives us the original equation $y = x - 2$.)

Note that the line at infinity in this example is the two-dimensional linear subspace given by $z = 0$.

Dualising in projective geometry is easy: we send every point and every line to its orthogonal complement. Thus, lines become points and vice versa, and it is easy to see that incidence is preserved (if $p \subseteq \ell$, then $\ell^\perp \subseteq p^\perp$ by elementary linear algebra).

I tried to find the projective interpretation of the duality given in the book by De Berg et al. Note that the point $(0,0)$ is sent to the line $y = 0$; therefore we have a point that is incident with its dual. This is a problem in the projective setting, for no one-dimensional subspace of $\mathbb{R}^3$ is contained in its orthogonal complement. We therefore have to identify the dual plane with some affine hyperplane $\mathcal B \subseteq \mathbb{R}^3$ different from $\mathcal A$. However, there is not much choice left for us: every vertical line in the primal plane must go to a point at infinity. If we embed a vertical line into the projective plane, we see that its dual is a one-dimensional subspace of the $xz$-plane. Therefore $\mathcal B$ must be parallel to $xz$-plane! This doesn't leave a lot of choice, although we still have some options. Let us go with $\mathcal B = \{(x,y,z) \in \mathbb{R}^3 \: : \: y = -1\}$, for reasons of symmetry. (Recall that $\mathcal A$ is the plane $z = -1$, so it seams natural to go with the plane $y = -1$ here.)

As it turns out, this gives us precisely the duality from the book! Let us work out in detail what happens:

• A primal point $p = (p_x,p_y)$ becomes the linear span of the point $(p_x,p_y,-1)$. The orthogonal complement is the hyperplane given by $p_x\: x + p_y\:y -z = 0$. This hyperplane is projected onto the hyperplane $y = -1$, so that we find the line $$ p_x\:x - p_y - z = 0, $$ that is: $z = p_x\: x - p_y$. This is precisely the line we were hoping to find!
• A primal line $y = ax + b$ becomes the two-dimensional subspace $ax - y - bz = 0$. (After all, filling in $z = -1$ yields again the equation we started with.) The orthogonal complement is the span of the vector $(a,-1,-b)$. Projecting this onto the plane $y = -1$ gives us the point $(a,-b)$, as desired.

Now, how did I find the formula that fixes your proposed duality? I simply replaced the plane $\mathcal B = \{(x,y,z)\in\mathbb{R}^3 \: : \: y = -1\}$ by the plane $\mathcal B' = \{(x,y,z) \in \mathbb{R}^3 \: : \: y = 1\}$ and worked out the duality (embedding the primal plane into the projective plane, taking orthogonal complements, and projecting onto $\mathcal B'$). Since $\mathcal B'$ is the reflection of $\mathcal B$ in the $xz$-plane, I wouldn't be surprised to learn that this duality is order-reversing. But then again, I haven't checked...

Note that this recipe can be used to find other dualities as well. For instance, replace $\mathcal A$ by the plane $\mathcal A' = \{(x,y,z)\in\mathbb{R}^3 \: : \: z = 1\}$. Now if we use $\mathcal A'$ and $\mathcal B'$, we get a duality where the point $p = (p_x,p_y)$ is sent to the line $y = -p_x\: x - p_y$ and vice versa. This duality is again symmetrical, in the sense that the same formula works for going from the primal to the dual plane and vice versa. Perhaps the symmetric dualities are precisely the ones that preserve order? Maybe I'm being too optimistic now. Nevertheless, there is still much about plane duality left for you and me to discover!