Direction-preserving function: Difference between revisions

Content deleted Content added

Inline

Revision as of 11:56, 6 March 2020

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 grid 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]

Definitions

We consider functions whose domain is a subset of the integer grid $\mathbb {Z} ^{n}$ , and whose range is a subset of the Euclidean space $\mathbb {R} ^{n}$ . All examples are for $n=2$ .

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

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

Let X be a subset of $\mathbb {Z} ^{n}$ and f a function, $f:X\to \mathbb {R} ^{n}$ .

f is called direction preserving if, for any pair of cell-connected points x,y in X, for all $i\in [n]$ : $f_{i}(x)\cdot f_{i}(y)\geq 0$ . In other words: all components of the function f do not switch direction when moving between cell-connected points.^[1]

References

^ ^a ^b 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.
^ 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.
^ Yang, Zaifu (2009-12-01). "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.
^ Chen, Xi; Deng, Xiaotie (2006). Chen, Danny Z.; Lee, D. T. (eds.). "A Simplicial Approach for Discrete Fixed Point Theorems". Computing and Combinatorics. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 3–12. doi:10.1007/11809678_3. ISBN 978-3-540-36926-4.

[:0-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). "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.

[4] Chen, Xi; Deng, Xiaotie (2006). Chen, Danny Z.; Lee, D. T. (eds.). "A Simplicial Approach for Discrete Fixed Point Theorems". Computing and Combinatorics. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 3–12. doi:10.1007/11809678_3. ISBN 978-3-540-36926-4.

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
 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 grid points. It can be considered a discrete analogue of a [[continuous function]].
-The concept was first defined by Iimura.<ref name=":0">{{Cite journal|last=Iimura|first=Takuya|date=2003-09-01|title=A discrete fixed point theorem and its applications|url=http://www.sciencedirect.com/science/article/pii/S0304406803000077|journal=Journal of Mathematical Economics|language=en|volume=39|issue=7|pages=725–742|doi=10.1016/S0304-4068(03)00007-7|issn=0304-4068}}</ref><ref>{{Cite journal|last=Iimura|first=Takuya|last2=Murota|first2=Kazuo|last3=Tamura|first3=Akihisa|date=2005-12-01|title=Discrete fixed point theorem reconsidered|url=http://www.sciencedirect.com/science/article/pii/S030440680500039X|journal=Journal of Mathematical Economics|language=en|volume=41|issue=8|pages=1030–1036|doi=10.1016/j.jmateco.2005.03.001|issn=0304-4068}}</ref> Some variants of it were later defined by Yang.<ref>{{Cite journal|last=Yang|first=Zaifu|date=2009-12-01|title=Discrete fixed point analysis and its applications|url=https://doi.org/10.1007/s11784-009-0130-9|journal=Journal of Fixed Point Theory and Applications|language=en|volume=6|issue=2|pages=351–371|doi=10.1007/s11784-009-0130-9|issn=1661-7746}}</ref>
+The concept was first defined by Iimura.<ref name=":0">{{Cite journal|last=Iimura|first=Takuya|date=2003-09-01|title=A discrete fixed point theorem and its applications|url=http://www.sciencedirect.com/science/article/pii/S0304406803000077|journal=Journal of Mathematical Economics|language=en|volume=39|issue=7|pages=725–742|doi=10.1016/S0304-4068(03)00007-7|issn=0304-4068}}</ref><ref>{{Cite journal|last=Iimura|first=Takuya|last2=Murota|first2=Kazuo|last3=Tamura|first3=Akihisa|date=2005-12-01|title=Discrete fixed point theorem reconsidered|url=http://www.sciencedirect.com/science/article/pii/S030440680500039X|journal=Journal of Mathematical Economics|language=en|volume=41|issue=8|pages=1030–1036|doi=10.1016/j.jmateco.2005.03.001|issn=0304-4068}}</ref> Some variants of it were later defined by Yang,<ref>{{Cite journal|last=Yang|first=Zaifu|date=2009-12-01|title=Discrete fixed point analysis and its applications|url=https://doi.org/10.1007/s11784-009-0130-9|journal=Journal of Fixed Point Theory and Applications|language=en|volume=6|issue=2|pages=351–371|doi=10.1007/s11784-009-0130-9|issn=1661-7746}}</ref> Chen and Deng.<ref>{{Cite journal|last=Chen|first=Xi|last2=Deng|first2=Xiaotie|date=2006|editor-last=Chen|editor-first=Danny Z.|editor2-last=Lee|editor2-first=D. T.|title=A Simplicial Approach for Discrete Fixed Point Theorems|url=https://link.springer.com/chapter/10.1007/11809678_3|journal=Computing and Combinatorics|series=Lecture Notes in Computer Science|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=3–12|doi=10.1007/11809678_3|isbn=978-3-540-36926-4}}</ref>
 == Definitions ==
@@ Line 10: / Line 10: @@
 Two points in <math>\mathbb{R}^n</math> are called ''cell connected'' if there is a cell that contains both of them.
-Let ''V'' be a subset of <math>\mathbb{Z}^n</math> and ''f'' a function, <math>f: V\to \mathbb{R}^n</math>.
+Let ''X'' be a subset of <math>\mathbb{Z}^n</math> and ''f'' a function, <math>f: X\to \mathbb{R}^n</math>.
-''f'' is called '''direction preserving''' if, for any pair of cell-connected points ''x'',''y'',  for all <math>i\in [n]</math>: <math>f_i(x)\cdot f_i(y) \geq 0</math>. In other words: all components of the function f do not switch direction when moving between cell-connected points.<ref name=":0" />
+''f'' is called '''direction preserving''' if, for any pair of cell-connected points ''x'',''y'' in ''X,'' for all <math>i\in [n]</math>: <math>f_i(x)\cdot f_i(y) \geq 0</math>. In other words: all components of the function f do not switch direction when moving between cell-connected points.<ref name=":0" />
 == References ==