{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T11:31:24Z","timestamp":1648899084634},"reference-count":9,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2010,8]]},"abstract":"<jats:p> Polygonal chains are fundamental objects in many applications like pattern recognition and protein structure alignment. A well-known measure to characterize the similarity of two polygonal chains is the (continuous\/discrete) Fr\u00e9chet distance. In this paper, for the first time, we consider the Voronoi diagram of polygonal chains in d-dimension under the discrete Fr\u00e9chet distance. Given a set [Formula: see text] of n polygonal chains in d-dimension, each with at most k vertices, we prove fundamental properties of such a Voronoi diagram [Formula: see text]. Our main results are summarized as follows. <\/jats:p><jats:p> \u2022 The combinatorial complexity of [Formula: see text] is at most O(n<jats:sup>dk+\u220a<\/jats:sup>). <\/jats:p><jats:p> \u2022 The combinatorial complexity of [Formula: see text] is at least \u03a9(n<jats:sup>dk<\/jats:sup>) for dimension d = 1, 2; and \u03a9(n<jats:sup>d(k-1)+2<\/jats:sup>) for dimension d &gt; 2. <\/jats:p>","DOI":"10.1142\/s0218195910003396","type":"journal-article","created":{"date-parts":[[2010,9,8]],"date-time":"2010-09-08T05:18:16Z","timestamp":1283923096000},"page":"471-484","source":"Crossref","is-referenced-by-count":0,"title":["VORONOI DIAGRAM OF POLYGONAL CHAINS UNDER THE DISCRETE FR\u00c9CHET DISTANCE"],"prefix":"10.1142","volume":"20","author":[{"given":"SERGEY","family":"BEREG","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Texas at Dallas, Richardson, TX 75083, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KEVIN","family":"BUCHIN","sequence":"additional","affiliation":[{"name":"Department of Information and Computing Sciences, Universiteit Utrecht, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MAIKE","family":"BUCHIN","sequence":"additional","affiliation":[{"name":"Department of Information and Computing Sciences, Universiteit Utrecht, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MARINA","family":"GAVRILOVA","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Calgary, Calgary, Alberta T2N 1N4, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BINHAI","family":"ZHU","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Montana State University, Bozeman, MT 59717, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794265724"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195995000064"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1165-y"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187681"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/BF03018603"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1142\/S0219720008003278"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574384"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2007.0156"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195910003396","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:25:10Z","timestamp":1565137510000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195910003396"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8]]},"references-count":9,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2010,8]]}},"alternative-id":["10.1142\/S0218195910003396"],"URL":"https:\/\/doi.org\/10.1142\/s0218195910003396","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,8]]}}}