Zhijing George Mou
Bibliography

Below are my notes on the following patent.

Patent US20230351547A1, Methods and control systems that use dimensional-transform-based three-dimensional searching and voxel mapping. Published 02-November-2023. (Cached copy here.)

Definitions: Let a COORDINATE be an unsigned integer of bit-depth D (e.g., 32, 16, 8), thus a number in the range [0..2^D-1]. Let x,y,z be 3D coordinates of a POINT. DST is a space filling curve, or more sensibly a volume-visiting-order. More bits in a key means more minimum volumes visited in key order. Any prefix of b-out-of-B bits in a key identify a volume of 2^{B-b-1} minimum volumes. Let k be a Morton-encoded a.k.a. Z-order encoded, a.k.a. Dimensional Shuffle Transform a.k.a. DST KEY derived from x,y,z. k = DSTencode(x,y,z); (x,y,z) = DSTdecode(k); The bits of x, y, z, could be formed into a table of D row and 3 columns. The table being read off columnwise yields the coordinates x, y, z. The table being read off rowwise yields the key k. Same data, different ordering. x, y, z if 16 bits each, then k is 3*16=48 bits. Let DB be a sorted data store of N records, each record containing a key (which is its sort order) and possibly other values. Note that if the DB were instead a store of N points each comprising 3 coordinates, sorted first on x, then on y, then on z, then a rectangular range search would require O(N) evaluations, since x_min might be found anywhere, and once first encountered, linear search over the whole y range for any given value of x; then finding one, linear search of the whole z range for any given value of y. This is basically O(N) search, although some say O(N^(2/3)) search. Converting into a tree may or may not help. A key pair s,t (starting and, terminal keys) correspond to points (sx,sy,sz), (tx,ty,tz). Assume without loss of generality sx is the geometric region { x,y,z | sx<=x<=tx, sy<=y<=ty, sz<=z<=tz } The Keyspan-Length L = | [s,t] | = t - s + 1. The Geometric Volume V = | | = (tx - sx + 1) * (ty - sy + 1) * (tz - sz + 1); Given a voxel interpretation that every key references a minimum voxel volumn vv=1, L*vv = L. V is also a nonnegative integer, the count of voxels in the geometric volume. (Their volumes are counted in the same units, that is, vv.) Definitions: Precision = V/L (Volume over Length). Length of a space-filling sequence of voxels may be MUCH greater than the volume of the geometric region, since it may wander far. But opposite corners s, t, cannot be closer than the opposite corners of a perfect region. Therefore Precision is in (0..1] for any non-empty volume. Shared Prefix: s^t = s XOR t: the h high bits which are zero are those for which s and t have identical values, and until one is non-zero, the space is repeatedly subdivided but low and high opposite corners s & t remain both in the same subdivision of the whole space identified by the shared h-bit prefix. Pattern: "Let the high (mod 3) bits of s^t determine the split, with the zeroes in that 3bit uint indicating halves to ignore." and ones indicating halves to split apart. A decomposition of a canonical region s,t according to its Pattern should EXCLUDE subregions which are empty, because they are outside [s,t]. Right?