Abstract:
Renewed interest in ethical sourcing of diamonds has opened a host of inherently geometric problems related to matching diamond scans with previously archived scans from ethically sourced diamonds. We introduce the minimum width polyhedral annulus as a geometric polyhedral pointset pattern matching problem and provide (1+\eps)-approximation algorithms in O(\eps^{-d} n) for d-dimensions and O(n\log \eps^{-1} + \eps^{-2}) for 2-dimensions.