{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T13:16:40Z","timestamp":1648991800771},"reference-count":5,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2011,6]]},"abstract":"<jats:p> We present an embedding and search reduction which allow us to build the first data structure for the nearest neighbor search among small point sets with respect to the directed Hausdorff distance under translation. The search structure is non-heuristic in the sense that the quality of the results, the performance, and the space bound are guaranteed. <\/jats:p><jats:p> Let n denote the number of point sets in the data base, s the maximal size of a point set, and d the dimension of the points. The nearest neighbor of a query point set under the translation invariant directed Hausdorff distance can be approximated by one or several nearest neighbor searches for single points in the Euclidean embedding space \u211d<jats:sup>d<\/jats:sup>(s-1). The approximation factor is [Formula: see text] in case of even s and [Formula: see text] when s is odd. Depending on the direction of the Hausdorff distance either the number of queries or the space requirements are exponential in s. <\/jats:p><jats:p> Furthermore it is shown how to find the exact nearest neighbor under the directed Hausdorff distance without transformation of the point sets within some weaker time and space bounds. <\/jats:p>","DOI":"10.1142\/s0218195911003706","type":"journal-article","created":{"date-parts":[[2011,6,28]],"date-time":"2011-06-28T15:33:53Z","timestamp":1309275233000},"page":"369-381","source":"Crossref","is-referenced-by-count":0,"title":["APPROXIMATE NEAREST NEIGHBOR SEARCH UNDER TRANSLATION INVARIANT HAUSDORFF DISTANCE"],"prefix":"10.1142","volume":"21","author":[{"given":"CHRISTIAN","family":"KNAUER","sequence":"first","affiliation":[{"name":"Institute of Computer Science, Universit\u00e4t Bayreuth, 95440 Bayreuth, Germany"}]},{"given":"MARC","family":"SCHERFENBERG","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, Universit\u00e4t Bayreuth, 95440 Bayreuth, Germany"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1781"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293348"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.08.003"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(00)00120-5"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1109\/99.641604"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195911003706","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:23:57Z","timestamp":1565137437000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195911003706"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6]]},"references-count":5,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2011,6]]}},"alternative-id":["10.1142\/S0218195911003706"],"URL":"https:\/\/doi.org\/10.1142\/s0218195911003706","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6]]}}}