Diamonds are Forever in the Blockchain: Geometric Polyhedral Point-Set Pattern Matching

Abstract

Motivated by blockchain technology for supply-chain tracing of ethically sourced diamonds, we study geometric polyhedral point-set pattern matching as minimum-width polyhedral annulus problems under translations and rotations. We provide two $(1+\epsilon )$-approximation schemes under translations with $O({\epsilon }^{-d}n)$-time for $d$ dimensions and $O(n\log {\epsilon }^{-1}+{\epsilon }^{-2})$-time for two dimensions, and we give an $O(f^{d-1}{\epsilon }^{1-2d}n)$-time algorithm when also allowing for rotations, parameterized on $f$, which we define as the slimness of the point set.

8 pages, 5 figures, To appear in 34th Canadian Conference on Computational Geometry