In discrete mathematics, a direction-preserving function (or mapping) is a function on a discrete space, such as the integer grid, that (informally) does not change too drastically between two adjacent points.
It can be considered a discrete analogue of a continuous function.
[1][2] Some variants of it were later defined by Yang,[3] Chen and Deng,[4] Herings, van-der-Laan, Talman and Yang,[5] and others.
, where the domain X is a finite subset of the Euclidean space
ch(X) denotes the convex hull of X.
There are many variants of direction-preservation properties, depending on how exactly one defines the "drastic change" and the "adjacent points".
Regarding the "drastic change" there are two main variants: Regarding the "adjacent points" there are several variants: Specific definitions are presented below.
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
The term locally direction-preserving (LDP) is often used instead.
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,
[3]: Def.2.2 Every HDP function is HGDP, but the converse is not true.
The function fb 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):
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).
Note that, in an integral triangulation, every simplicially-connected points are also cell-connected, but the converse is not true.
Consider the integral triangulation that partitions it into two triangles: {(2,6),(2,7),(3,7)} and {(2,6),(3,6),(3,7)}.
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
[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,
[6][7][8] Every HGDP function is SGDP, but HGDP is much stronger: it is equivalent to SGDP w.r.t.
[3]: Def.2.3 As an example, the function fc 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.