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. ^{[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.

Basic concepts

We focus on functions ${\displaystyle f:X\to \mathbb {R} ^{n}}$, where the domain X is a finite subset of the Euclidean space ${\displaystyle \mathbb {R} ^{n}}$. 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:

• Direction preservation (DP) means that, if x and y are adjacent, then for all ${\displaystyle i\in [n]}$: ${\displaystyle f_{i}(x)\cdot f_{i}(y)\geq 0}$. In words: every component of the function f must not switch signs between adjacent points.
• Gross direction preservation (GDP) means that, if x and y are adjacent, then ${\displaystyle f(x)\cdot f(y)\geq 0}$. In words: the direction of the function f (as a vector) does not change by more than 90 degrees between adjacent points. Note that DP implies GDP but not vice versa.

Regarding the "adjacent points" there are several variants:

• Hypercubic means that x and y are adjacent iff they are contained in some axes-parallel hypercube of side-length 1.
• Simplicial means that x and y are adjacent iff they are vertices of the same simplex, in some triangulation of the domain. Usually, simplicial adjacency is much stronger than hypercubic adjacency; accordingly, hypercubic DP is much stronger than simplicial DP.

Specific definitions are presented below. All examples below are for ${\displaystyle n=2}$ dimensions and for X = { (2,6), (2,7), (3, 6), (3, 7) }.

Properties and examples

Hypercubic direction-preservation

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).

fa	6	7
2	(2,1)	(1,1)
3	(0,1)	(0,0)

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.

fb	6	7
2	(2,1)	(1,1)
3	(1,-1)	(0,0)

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.

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 ${\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}

fc	6	7
2	(2,1)	(1,1)
3	(1,-2)	(0,0)

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}$.

References

1. Iimura, Takuya (2003-09-01). "A discrete fixed point theorem and its applications". Journal of Mathematical Economics. 39 (7): 725–742. doi:10.1016/S0304-4068(03)00007-7. ISSN   0304-4068.
2. Iimura, Takuya; Murota, Kazuo; Tamura, Akihisa (2005-12-01). "Discrete fixed point theorem reconsidered". Journal of Mathematical Economics. 41 (8): 1030–1036. doi:10.1016/j.jmateco.2005.03.001. ISSN   0304-4068.
3. Yang, Zaifu (2009-12-01) [2004 (FBA working paper no. 210, Yokohama National University)]. "Discrete fixed point analysis and its applications". Journal of Fixed Point Theory and Applications. 6 (2): 351–371. doi:10.1007/s11784-009-0130-9. ISSN   1661-7746. S2CID   122640338.
4. Chen, Xi; Deng, Xiaotie (2006). "A Simplicial Approach for Discrete Fixed Point Theorems". In Chen, Danny Z.; Lee, D. T. (eds.). Computing and Combinatorics. Lecture Notes in Computer Science. Vol. 4112. Berlin, Heidelberg: Springer. pp. 3–12. doi:10.1007/11809678_3. ISBN   978-3-540-36926-4.
5. Jean-Jacques Herings, P.; van der Laan, Gerard; Talman, Dolf; Yang, Zaifu (2008-01-01). "A fixed point theorem for discontinuous functions". Operations Research Letters. 36 (1): 89–93. doi:10.1016/j.orl.2007.03.008. ISSN   0167-6377. S2CID   14117444.
6. Iimura, Takuya; Yang, Zaifu (2009-12-01). "A study on the demand and response correspondences in the presence of indivisibilities". Journal of Fixed Point Theory and Applications. 6 (2): 333–349. doi:10.1007/s11784-009-0131-8. ISSN   1661-7746. S2CID   121519442.
7. van der Laan, Gerard; Talman, Dolf; Yang, Zaifu (2007-01-01). "A Vector Labeling Method for Solving Discrete Zero Point and Complementarity Problems" (PDF). SIAM Journal on Optimization. 18 (1): 290–308. doi:10.1137/050646378. ISSN   1052-6234.
8. Yang, Zaifu (2008-11-01). "On the Solutions of Discrete Nonlinear Complementarity and Related Problems". Mathematics of Operations Research. 33 (4): 976–990. doi:10.1287/moor.1080.0343. ISSN   0364-765X.