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 + \varepsilon)$-approximation schemes under translations with $O(\varepsilon^{ -d} n)$-time for $d$ dimensions and $O(n\log \varepsilon^{ -1} + \varepsilon^{ -2})$-time for two dimensions, and we give an $O(f^{ d-1}\varepsilon^{ 1-2d}n)$-time algorithm when also allowing for rotations, parameterized on $f$, which we define as the slimness of the point set.
Categories: cs.CG