Point lattice to lattice mesh transformation nomenclature

Question

I am currently struggling with some nomenclature for my thesis. When I have a point lattice, I can create a mesh lattice by connecting the nearest lattice points with edges. When I have a mesh lattice, I can create a point lattice by removing all edges. I am confused on how to call the process of transforming one into the other, any suggestions?

Answer 1

Let us define a "lattice with distances" as a (not necessarily connected) lattice equipped with an edge-length function: $L = \{ \{V\}, \{E\}, d \}$ where

• $\{V\}$ is a (finite or countably infinite) set of abstract "vertices" each of which which we shall refer to as $v_i$;

• $\{E\}$ is a set of (unordered) pairs $v_i, v_j$ which we can label $e_{ij}$;

• $d$ is a function $d : E \to \Bbb R^+$ mapping each $e_{ij}$ to a real-valued distance $d(e_{ij})$

For notational convenience let us define the "priority" of $e_{ij}$ with respect to $v_i$ as the number of edges $e_{ik}$ with $k \neq j$ such that $d(e_{ik}) < d(e_{ij})$. If $m$ is distinct from $i$ and $j$ define the priority of $e_{ij}$ with respect to $v_m$ to be infinite.

Note that in the definition of priority $\mbox{pr}(e_{ij};v_i)$, one of the vertices of all the edges being compared is $v_i$. Thus $\mbox{pr}(e_{ij};v_i) = 0 \Longleftrightarrow e_{ij}$ connects $v_i$ with a nearest neighbor $v_j$. (There can be multiple nearest neighbors, that is, multiple neighbors all the same distance from $v_i$ such that no other neighbor is closer.)

Now let us define a $k$-prune of $L$ as $$ k\mbox{-prune} (\, \{ \{V\}, \{E\}, d \}\, ) = \{ \{V\}, \{e_{ij} : \exists v_m : \mbox{pr}((e_{ij};v_m) < k\}, d \} $$

Then in this formalism, the process of transforming the full ("mesh") lattice $L$ to a corresponding point lattice $P$ is

$$ L \to P = 0\mbox{-prune}(L)$$

That answers one direction of your question.

More interesting is when you do a $1\mbox{-prune}$, leaving only the edges which connect some vertex to its nearest neighbor. For example, one might conjecture (incorrectly) that the $1\mbox{-prune}$ of a connected lattice must be connected.

For the other direction, we need one additional concept. We say that a lattice $L_1 = \{ \{V\}, \{E\}_1, d \}$ is embedded in a lattice $L_2 = \{ \{V\}, \{E\}_2 \supset \{E\}_1, d \}$ is a subset of the set of edges of the embedding lattice, and the distance function is the restriction of the distance function of the embedding lattice to the set of edges of $L_1$. With a minor abuse of notation, we shall say $L_1 \subset_v L_2$ with the subscript $v$ there to remind us that the sets of vertices are identical.

For the question you have in mind, you probably envision $L_2$ to be a complete lattice, such that for any pair of vertices, the edge connecting them is in $L_2$, but in principle you can work without that assumption.

And now we are ready to define the transformation in the other part of your question.

Given a point lattice $P$ and an embedding lattice $L$ such that $P \subset_v L$ then we can transform

$$ P \to L_1 = 1\mbox{-prune}(L)$$

It is easy to see that every vertex in $P$ is also in $L_1$, and that very vertex in $L_1$ is connected to one or more other vertices, and every such connection is a minimum-distance edge with respect to one (or both) of its endpoints.

This answer to the second part of the question takes you around the long way -- we first embed the point lattice into something which may have many more edges, then prune that down to the desired lattice.

This long way, or something like it, is inevitable: If you don't embed the point lattice into something defining distances between points, then you can't talk about forming a lattice from a point lattice by adding the nearest neighbor edges.