Direction-preserving function

A cell is a subset of ${\displaystyle \mathbb {R} ^{n}}$ that can be expressed by ${\displaystyle k+[0,1]^{n}}$ for some ${\displaystyle k\in \mathbb {Z} ^{n}}$. For example, the square ${\displaystyle [2,3]\times [6,7]}$ is a cell.

Two points in ${\displaystyle \mathbb {R} ^{n}}$ are called cell connected if there is a cell that contains both of them.

Hypercubic direction-preservation properties require that the function does not change too drastically in cell-connected points (points in the same hypercubic cell).

f is called hypercubic direction preserving (HDP) if, for any pair of cell-connected points x,y in X, for all ${\displaystyle i\in [n]}$: ${\displaystyle f_{i}(x)\cdot f_{i}(y)\geq 0}$. The term locally direction-preserving (LDP) is often used instead.[1] The function f^a on the right is DP.

• Some authors[4]^: Def.1 use a variant requiring that, for any pair of cell-connected points x,y in X, for all ${\displaystyle i\in [n]}$: ${\displaystyle (f_{i}(x)-x_{i})\cdot (f_{i}(y)-y_{i})\geq 0}$. A function f(x) is HDP by the second variant, iff the function g(x):=f(x)-x is HDP by the first variant.

f is called hypercubic gross direction preserving (HGDP), or locally gross direction preserving (LGDP), if for any pair of cell-connected points x,y in X, ${\displaystyle f(x)\cdot f(y)\geq 0}$.[3]^: Def.2.2 Every HDP function is HGDP, but the converse is not true. The function f^b is HGDP, since the scalar product of every two vectors in the table is non-negative. But it is not HDP, since the second component switches sign between (2,6) and (3,6): ${\displaystyle f_{2}^{b}(2,6)\cdot f_{2}^{b}(3,6)=-1<0}$.

• Some authors[5] use a variant requiring that, for any pair of cell-connected points x,y in X, ${\displaystyle (f(x)-x)\cdot (f(y)-y)\geq 0}$. A function f(x) is HGDP by the second variant, iff the function g(x):=f(x)-x is HGDP by the first variant.

A simplex is called integral if all its vertices have integer coordinates, and they all lie in the same cell (so the difference between coordinates of different vertices is at most 1).

A triangulation of some subset of ${\displaystyle \mathbb {R} ^{n}}$ is called integral if all its simplices are integral.

Given a triangulation, two points are called simplicially connected if there is a simplex of the triangulation that contains both of them.

Note that, in an integral triangulation, every simplicially-connected points are also cell-connected, but the converse is not true. For example, consider the cell ${\displaystyle [2,3]\times [6,7]}$. Consider the integral triangulation that partitions it into two triangles: {(2,6),(2,7),(3,7)} and {(2,6),(3,6),(3,7)}. The points (2,7) and (3,6) are cell-connected but not simplicially-connected.

Simplicial direction-preservation properties assume some fixed integral triangulation of the input domain. They require that the function does not change too drastically in simplicially-connected points (points in the same simplex of the triangulation). This is, in general, a much weaker requirement than hypercubic direction-preservation.

f is called simplicial direction preserving (SDP) if, for some integral triangulation of X, for any pair of simplicially-connected points x,y in X, for all ${\displaystyle i\in [n]}$: ${\displaystyle (f_{i}(x)-x_{i})\cdot (f_{i}(y)-y_{i})\geq 0}$.[4]^: Def.4

f is called simplicially gross direction preserving (SGDP) or simplicially-local gross direction preserving (SLGDP) if there exists an integral triangulation of ch(X) such that, for any pair of simplicially-connected points x,y in X, ${\displaystyle f(x)\cdot f(y)\geq 0}$.[6][7][8]

Every HGDP function is SGDP, but HGDP is much stronger: it is equivalent to SGDP w.r.t. all possible integral triangulations of ch(X), whereas SGDP relates to a single triangulation.[3]^: Def.2.3 As an example, the function f^c on the right is SGDP by the triangulation that partitions the cell into the two triangles {(2,6),(2,7),(3,7)} and {(2,6),(3,6),(3,7)}, since in each triangle, the scalar product of every two vectors is non-negative. But it is not HGDP, since ${\displaystyle f^{c}(3,6)\cdot f^{c}(2,7)=-1<0}$.