Lattice lambada

For many scale-dependent features, a space partition of some sorts is needed for finding a possible scale interval where the feature is meaningful and approximately constant. The overlap ratio $\lambda$ of two point sets was defined by:  \[\lambda_\epsilon(A,B)= \frac{|\{A\}_\epsilon \cap \{B\}_\epsilon|}{|\{A\}_\epsilon \cup \{B\}_\epsilon|}\]

And the earlier post mentioned, that it can be improved by a shift: \[\lambda:= \left(\lambda_\epsilon(A,B)+ \lambda_\epsilon(A+\mathbf{1}_A\epsilon/2, B+\mathbf{1}_B\epsilon/2)\right)/2, \] where $\mathbf{1}_A$ is a $|A|\times d$ matrix filled with ones. The term $\mathbf{1}\,\epsilon/2$ shifts the rounding creating a different version of $\lambda$ calculation. Averaging from the two versions stabilizes the scale-dependent features.

Shifted rounding grid (red).

Rounded sets can be formed by hexagonal lattice arrangement, too. And the shifting trick can be utilized there, too. A hexagonal lattice has the following matrix $E=(n_1\,n_2\,n_3)$: 

\[E= \begin{pmatrix} 1 & 1/2 & 1/2 \\ 0 & \sqrt{3}/2 & 1/(2\sqrt{3}) \\ 0 & 0  & \sqrt{2/3}  \end{pmatrix}.\] 

Now, any given point $p\in \mathbb{R}^3$ has a unique projection \[\nu^*=\text{arg min}_{\nu\in\mathbb{Z}^3} \|p-E\nu\|\] to the lattice indices $\nu$ and this can be found by rounding. So, for a scale $\epsilon$: \[\{P\}_\epsilon=\{E\,\text{round}(E^{-1}p/\epsilon)\epsilon\,|\,  p\in P\}.\]

The 2D case follows by removing the last row and column from the matrix $E$. The orthogonal rounding had $c= \mathbf{1}\epsilon/2$ as the crucial shift for the shifted rounding. Now, we use $c=\left(1/2,\,1/(2\sqrt{3}),\,1/(2\sqrt{6})\right)\epsilon$, where $c=\sum_i n_i/4$ is the center of an tetrahedron, when $n_i$ are the three vertices and origo is the fourth one. Happiness abounds, since the hexagonal rounding gives much better selection $C\subset A$ of sparse subsets $C=NN(\{A\}_\epsilon,A\}$, and the stable scale interval is usually wider with any scale-dependent feature. 

Just as in a previous article, black dots are $A$, magenda crosses are $\{A\}_\epsilon$ and members of $C$ are depicted by red circles. One can see that the packing ratio of $C$ has gone from $l/l_0\approx 1.05$ to close to 1. 

A  synthetic test set $A$ and a subset selection $NN(\{A\}_\epsilon, A)$ by hexagonal rounding.

 

An example of the overlap factor $\lambda$ in the case of point sets $A$ and $B$ of the previous blog post had a block rounding (or cubic rounding) as the black curve in the Fig. below.  Red line is the overlap estimate from the local insidence histogram. And blue is the hexagonal rounding by different scale factors $\epsilon$, and the dashed blue line is the shifted hexagonal rounding. As one can see, the hexagonal rounding is more stable on the scale interval 2...8 m than the cubic rounding. Surprisingly, the hexagonal rounding is more unstable above this scale reaching $\lambda=1$. The case of PCs A and B is actually a rather difficult one. Different exampels give much better and more unisono results.

Overlap estimates by hexagonal rounding, cubic rounding and shifted hexagonal rounding are being compared to original cubic rounding.