Direction-preserving function

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.
The concept was first defined by Iimura. Some variants of it were later defined by Yang, Chen and Deng, Herings, van-der-Laan, Talman and Yang, and others.
Basic concepts.
We focus on functions formula_1, where the domain X is a finite subset of the Euclidean space formula_2. 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. All examples below are for formula_6 dimensions and for "X" = { (2,6), (2,7), (3, 6), (3, 7) }.
Properties and examples.
Hypercubic direction-preservation.
A "cell" is a subset of formula_2 that can be expressed by formula_8 for some formula_9. For example, the square formula_10 is a cell.
Two points in formula_2 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 formula_3: formula_4. The term locally direction-preserving (LDP) is often used instead. The function "fa" on the right is DP.
"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," formula_5. 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): formula_17.
Simplicial direction-preservation.
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 formula_2 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 formula_10. 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 formula_3: formula_15.
"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," formula_5.
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. 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. But it is not HGDP, since formula_24.