Testwiki:Reference desk/Archives/Mathematics/2022 November 10

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < November 9 ! width="25%" align="center"|<< Oct | November | Dec >> ! width="20%" align="right" |Current desk > |}

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 10

Locality-preserving functions

Having a problem with locality-preserving functions. In particular, a locality-preserving hash function $f:ℳ\to ℝ$ (where $ℳ=(M,d)$ is a metric space) is a hash function satisfying $\mathrm{\forall }p,q,r\in ℳ,d(p,q)<d(q,r)\Rightarrow |f(p)-f(q)|<|f(q)-f(r)|$, and more generally, we can say that a locality-preserving function $f:ℳ\to 𝒦$ for metric spaces $ℳ=(M,d_M),𝒦=(K,d_K)$ is a function satisfying $\mathrm{\forall }p,q,r\in ℳ,d_M(p,q)<d_M(q,r)\Rightarrow d_K(f(p),f(q))<d_K(f(q),f(r))$.

It can be seen that any such function must be injective. If $f(p)=f(q)$ but $p\ne q$, then for any $r\in ℳ$ with $d_M(p,r)\ne d_M(q,r)$ (for example, $p$ or $q$ itself), we must have either $d_M(p,r)<d_M(q,r)$ or $d_M(p,r)>d_M(q,r)$, but $d_K(f(p),f(r))=d_K(f(q),f(r))$, which is contradictory.

The area I'm having trouble with is that I have no idea if locality-preserving functions have to be continuous. I'm pretty sure I have it narrowed down to one problem which I am completely stuck on: if $f:ℳ\to 𝒦$ is a locality-preserving function, is it possible for there to be some point $x\in ℳ$ such that $x$ is an accumulation point but $f(x)$ is an isolated point? Similar problem in establishing whether $f$ is an open mapping, where the problem becomes whether it is possible for $x$ to be an isolated point while $f(x)$ is an accumulation point.

As a quick aside, I'm fairly sure that if $𝒦$ (resp. $ℳ$) is compact, then the answer is no for continuity (resp. open mapping) GalacticShoe (talk) 04:22, 10 November 2022 (UTC)

Neither one needs to hold. For instance, let $ℳ=\{0\}\cup \{\frac{1}{n}:n\in {\mathbb{Z}}^{+}\}$, $𝒦={\ell }^{\mathrm{\infty }}(ℝ)$ under the supremum norm, and $f(0)=e_1$, $f\left(\frac{1}{n}\right)=\frac{n+1}{n}{e}_{n+1}$ (where $e_i$ is the sequence with 1 in the $i$-th position and 0 elsewhere). $f$ is a locality-preserving function and 0 is an accumulation point of $ℳ$, but $f(0)=e_1$ is an isolated point of $f(ℳ)$. The inverse of $f$ is also a locality-preserving function from $f(ℳ)$ back to $ℳ$. (Wrong, see below for a correct example.) BentSm (talk) 05:58, 10 November 2022 (UTC)

Writing $f:ℳ\to 𝒮,$ is the codomain $𝒮$ in this proposed counterexample one of scalar values?  --Lambiam 10:27, 10 November 2022 (UTC)

No. (I was basing my answer from his (extended) definition of a locality-preserving function.) BentSm (talk) 01:08, 11 November 2022 (UTC)

Hey BentSM, thanks for the response! Just wanted to clarify a point of confusion; is the distance under the supremum norm defined as $d_{sup}(x,y)=su{p}_n|x_n-y_n|$, and if so, would $|0-\frac{1}{3}|=\frac{1}{3}>\frac{1}{6}=|\frac{1}{3}-\frac{1}{2}|,d_{sup}(f(0),f(\frac{1}{3}))=\frac{4}{3}<\frac{3}{2}=d_{sup}(f(\frac{1}{3}),f(\frac{1}{2}))$ not render $f$ non-locality preserving? Thanks again! GalacticShoe (talk) 18:07, 11 November 2022 (UTC)

You're quite right. This does work, though:

$ℳ=\{0\}\cup \{\frac{1}{n}:n\in {\mathbb{Z}}^{+}\}$, $𝒦={\ell }^{\mathrm{\infty }}(ℝ)$ under the $L^1$ norm, and $f(0)=e_2$, $f\left(\frac{1}{n}\right)=\frac{1}{n}{e}_1+e_{n+2}$. If $x\ne y$, $d_1(f(x),f(y))=2+|x-y|$ ($d_1(f(x),f(x))=0$, of course). BentSm (talk) 00:32, 12 November 2022 (UTC)

Suppose we want to hash (one-dimensional) real values into integer-valued buckets. So the desired hash function has signature $f:ℝ\to \mathbb{Z}.$ A prime candidate is the rounding function defined by

$f(x)=\lfloor x+0.5\rfloor .$

If any function from the reals to the integers is a locality-preserving hash, this should be one. But (under the usual metric in which $d(x,y)=|x-y|$ ) we have

$d(3.4,3.6)=0.2<d(3.6,3.9)=0.3,$

whereas

$|f(3.4)-f(3.6)|=|3-4|=1>|f(3.6)-f(3.9)|=|4-4|=0.$

This suggest strongly that the given definition is off. Perhaps it should be the other way around: values mapped to the same bucket should be close. That would explain the suggested relation to space-filling curves: themselves being continuous, they are surjective and so have a (not unique) inverse. Such an inverse can be viewed as a hash, and pairs of points whose hashes are close are themselves close. Naively reversing the implication does not work, however:

$|f(2.8)-f(3.4)|=|3-3|=0<|f(3.4)-f(3.6)|=|3-4|=1,$

whereas

$d(2.8,3.4)=0.6>d(3.4,3.6)=0.2.$

So we may want a condition in the shape of

$|f(x)-f(y)|<\epsilon \Rightarrow d(x,y)<\delta .$

 --Lambiam 12:11, 10 November 2022 (UTC)

I do agree that the definition is rather unusual. It is certainly is not that of the two references listed in the corresponding section of the Wikipedia article referenced. I tried doing some searching, which turned up more references to "locality-preserving" than direct definitions; see, e.g., [1], [2], [3], [4]. For what it's worth, none of what I found matched up with the definition given in the article (except for one site that cites Wikipedia). BentSm (talk) 03:38, 11 November 2022 (UTC)

For example, the Hilbert curve satisfies this "inverse continuity" condition if we put $\delta =\sqrt{c\epsilon },$ where I think we can take $c=\frac{27}{5}.$  --Lambiam 16:11, 10 November 2022 (UTC)

Slopes and angles

If a line had a slope of S (assuming the line goes through the origin and S cannot be negative), how can I use that to find out the angle that the line makes with the X or Y-axis? Primal Groudon (talk) 14:18, 10 November 2022 (UTC)

By consulting our article Slope: it gives the relation between the slope of a line and its angle of inclination. It is not relevant whether the line goes through the origin, and the relation is valid regardless of the sign of the slope.  --Lambiam 16:35, 10 November 2022 (UTC)

• The angle of the line to the X axis will be the arctan of the slope. That's because t the line will always be the hypotenuse of a right triangle where the X axis is one leg and a line parallel to the Y axis is the other leg. Since tangent Θ = Y/X = slope, to find the angle Θ you take the inverse tangent (arctan) of the slope. --2600:1004:B024:84EE:F02:CC26:4A9A:E65 (talk) 21:54, 10 November 2022 (UTC)

There's two angles corresponding to a slope differing by 180°. Very often you'll want the one between -90° and +90°. I'm not sure why you specified that the slope is not negative, that doesn't matter much. If anything the slope that is a bit peculiar is the vertical slope going straight up and down where the ratio is infinity. NadVolum (talk) 01:19, 11 November 2022 (UTC)