Abstract
Locality Sensitive Hashing (LSH) is an effective method of indexing a set of items to support efficient nearest neighbors queries in highdimensional spaces. The basic idea of LSH is that similar items should produce hash collisions with higher probability than dissimilar items.
We study LSH for (not necessarily convex) polygons, and use it to give efficient data structures for similar shape retrieval. Arkin et al. [Arkin et al., 1991] represent polygons by their "turning function"  a function which follows the angle between the polygon’s tangent and the xaxis while traversing the perimeter of the polygon. They define the distance between polygons to be variations of the L_p (for p = 1,2) distance between their turning functions. This metric is invariant under translation, rotation and scaling (and the selection of the initial point on the perimeter) and therefore models well the intuitive notion of shape resemblance.
We develop and analyze LSH near neighbor data structures for several variations of the L_p distance for functions (for p = 1,2). By applying our schemes to the turning functions of a collection of polygons we obtain efficient near neighbor LSHbased structures for polygons. To tune our structures to turning functions of polygons, we prove some new properties of these turning functions that may be of independent interest.
As part of our analysis, we address the following problem which is of independent interest. Find the vertical translation of a function f that is closest in L₁ distance to a function g. We prove tight bounds on the approximation guarantee obtained by the translation which is equal to the difference between the averages of g and f.
BibTeX  Entry
@InProceedings{kaplan_et_al:LIPIcs.STACS.2021.46,
author = {Kaplan, Haim and Tenenbaum, Jay},
title = {{Locality Sensitive Hashing for Efficient Similar Polygon Retrieval}},
booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
pages = {46:146:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771801},
ISSN = {18688969},
year = {2021},
volume = {187},
editor = {Bl\"{a}ser, Markus and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13691},
URN = {urn:nbn:de:0030drops136910},
doi = {10.4230/LIPIcs.STACS.2021.46},
annote = {Keywords: Locality sensitive hashing, polygons, turning function, L\underlinep distance, nearest neighbors, similarity search}
}
Keywords: 

Locality sensitive hashing, polygons, turning function, L_p distance, nearest neighbors, similarity search 
Collection: 

38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) 
Issue Date: 

2021 
Date of publication: 

10.03.2021 