{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T23:40:52Z","timestamp":1769557252451,"version":"3.49.0"},"reference-count":10,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2012,2]]},"abstract":"<jats:p> We consider the problem of computing the discrete Fr\u00e9chet distance between two polygonal curves when their vertices are imprecise. An imprecise point is given by a region and this point could lie anywhere within this region. By modelling imprecise points as balls in dimension d, we present an algorithm for this problem that returns in time 2<jats:sup>O(d<jats:sup>2<\/jats:sup>)<\/jats:sup> m<jats:sup>2<\/jats:sup>n<jats:sup>2<\/jats:sup> log <jats:sup>2<\/jats:sup>(mn) the minimum Fr\u00e9chet distance between two imprecise polygonal curves with n and m vertices, respectively. We give an improved algorithm for the planar case with running time O(mn log <jats:sup>3<\/jats:sup>(mn) + (m<jats:sup>2<\/jats:sup>+n<jats:sup>2<\/jats:sup>) log (mn)). In the d-dimensional orthogonal case, where points are modelled as axis-parallel boxes, and we use the L<jats:sub>\u221e<\/jats:sub> distance, we give an O(dmn log (dmn))-time algorithm. <\/jats:p><jats:p> We also give efficient O(dmn)-time algorithms to approximate the maximum Fr\u00e9chet distance, as well as the minimum and maximum Fr\u00e9chet distance under translation. These algorithms achieve constant factor approximation ratios in \"realistic\" settings (such as when the radii of the balls modelling the imprecise points are roughly of the same size). <\/jats:p>","DOI":"10.1142\/s0218195912600023","type":"journal-article","created":{"date-parts":[[2012,9,12]],"date-time":"2012-09-12T09:32:56Z","timestamp":1347442376000},"page":"27-44","source":"Crossref","is-referenced-by-count":11,"title":["COMPUTING THE DISCRETE FR\u00c9CHET DISTANCE WITH IMPRECISE INPUT"],"prefix":"10.1142","volume":"22","author":[{"given":"HEE-KAP","family":"AHN","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, POSTECH, Pohang, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CHRISTIAN","family":"KNAUER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MARC","family":"SCHERFENBERG","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, Universit\u00e4t Bayreuth, 95440 Bayreuth, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"LENA","family":"SCHLIPF","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, Freie Universit\u00e4t Berlin, 14195 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ANTOINE","family":"VIGNERON","sequence":"additional","affiliation":[{"name":"Geometric Modeling and Scientific Visualization Center, King Abdullah University of Science and Technology, Thuwal, Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,9,12]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1145\/299917.299918"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1038"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000064"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1042-5"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511530067"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1137\/0213002"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.01.039"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2008.12.007"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0935-6"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2005.01.004"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195912600023","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T19:00:38Z","timestamp":1565118038000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195912600023"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2]]},"references-count":10,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2012,9,12]]},"published-print":{"date-parts":[[2012,2]]}},"alternative-id":["10.1142\/S0218195912600023"],"URL":"https:\/\/doi.org\/10.1142\/s0218195912600023","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2]]}}}