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

08/11/2022
by   Gill Barequet, et al.
0

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 + ε)-approximation schemes under translations with O(ε^-d n)-time for d dimensions and O(nlogε^-1 + ε^-2)-time for two dimensions, and we give an O(f^d-1ε^1-2dn)-time algorithm when also allowing for rotations, parameterized on f, which we define as the slimness of the point set.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset