Pasting gauges. I: Shortest paths across a hyperplane (Q1728102): Difference between revisions

In the paper under review, the author studies the largest quasimetric in \(\mathbb{R}^{d}\) no greater than one given gauge on one side of a fixed hyperplane, and another gauge on the other side. Let us recall basic definitions and the main construction of the paper. A gauge is a real-valued function \(\gamma\) everywhere defined on a finite dimensional real vector space \(\mathbb{R}^{d}\) satisfying the following properties for any \(x, y\) \begin{itemize} \item[(G1)] \(\gamma(x)\geq 0\), \item[(G2)] \(\gamma(x) = 0\) iff \(x=0\), \item[(G3)] \(\gamma(rx) = r\cdot \gamma(x)\) for any \(r\geq 0\), \item[(G4)] \(\gamma(x+y) \leq \gamma(x) + \gamma(y)\). \end{itemize} A gauge \(\gamma\) is a norm if it satisfies \(\gamma(x) = \gamma(-x)\), and it defines a (oriented) distance measure \(d_{\gamma}\) by \[ d_{\gamma}(x,y) = \gamma(x-y) \] which satisfies for any \(x,y,z\) the following conditions \begin{itemize} \item[(D1)] \(d_{\gamma}(x,y) \geq 0\), \item[(D2)] \(d_{\gamma}(x,y)=0\) iff \(x=y\), \item[(D3)] \(d_{\gamma}(x,y) \leq d_{\gamma}(x,z) + d_{\gamma}(z,y)\) (oriented triangle inequality). \end{itemize} If additionally \(\gamma\) is a norm, then \(d_{\gamma}\) is a metric. Given two gauges \(\phi, \psi\) and a hyperplane \(H\) splitting \(\mathbb{R}^{d}\) into two closed halfspaces \(H_{\phi}\) and \(H_{\psi}\), one wants to construct an (asymmetric) distance measure \(d\) on \(\mathbb{R}^{d}\) satisfying the following properties: \begin{itemize} \item[(d1)] for any \(x,y \in H_{\phi}\) we have \(d(x,y) \leq d_{\phi}(x,y) = \phi(x-y)\), \item[(d2)] for any \(x,y \in H_{\psi}\) we have \(d(x,y) \leq d_{\psi}(x,y) = \psi(x-y)\), \item[(d3)] \(d\) is as large as possible. \end{itemize} At the first glance, it is not directly evident that such a \(d\) should always exist. Now we are going to present the main construction. We define \(\delta(p,q)\) which is equal to either \(\phi(q-p)\) when \(p,q \in H_{\phi}\) not both on \(H\), \(\psi(q-p)\) when \(p,q \in H_{\psi}\) not both on \(H\), or \(\min \{\phi(q-p), \psi(q-p)\}\) when \(p,q\in H\). We call a \(H\)-path \(\mathcal{P}\) any finite sequence of points in \(\mathbb{R}^{d}\) such that any two consecutive ones belong either both to \(H_{\phi}\) or both to \(H_{\psi}\). The first point of a \(H\)-path \(\mathcal{P}\) is called its source and its last point is called its destination. If \(\mathcal{P}\) has source \(a\) and destination \(b\), then we say that \(\mathcal{P}\) is from \(a\) to \(b\). A segment connecting two consecutive points of \(\mathcal{P}\) is called a \(\mathcal{P}\)-link. The length \(\ell(\mathcal{P})\) of a \(H\)-path \(\mathcal{P}\) is defined as the sum of all distances between consecutive pairs of points of \(\mathcal{P}\) using the distance vaild for this pair. In other words, for a \(H\)-path \(\mathcal{P} = (p_{0}, \dots, p_{n})\) we define \[ \ell(\mathcal{P}) = \sum_{i=1}^{n} \delta(p_{i-1},p_{i}). \] Now we may define the following measure \[ d(a,b) = \inf \{ \ell(\mathcal{P}) : \mathcal{P} \text{ is a } H\text{-path from } a \text{ to } b \}. \] Theorem. \(d\) defined as above is a distance measure satisfying all sought properties (D1--D3) and (d1--d3). \(d\) is a metric iff both \(\phi\) and \(\psi\) are norms. An \(aH\)-path is an alternating \(H\)-path, which means that no two consecutive links on the path have their \(\delta\)-length measured by a same gauge. We call \(aH3\)-path an \(aH\)-path that consists of at most \(3\) links (\(4\)-points). Lemma. \(d(a,b) = \min \{\ell(\mathcal{P}) : \mathcal{P} \text{ is an } aH3\text{-path from } a \text{ to } b\}.\) Futhermore, the author obtains exact optimality conditions for any single-, double-, or triple-link path and provides explicit algorithms to construct shortest paths in general and between any two given points in \(\mathbb{R}^{d}\).