{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,10]],"date-time":"2023-01-10T18:08:14Z","timestamp":1673374094527},"reference-count":0,"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":[[1993,9]]},"abstract":"<jats:p> Efficient online algorithms are presented for maintaining the (almost-exact) width and diameter of a dynamic planar point-set, S. Let n be the number of points currently in S, let W and D denote the width and diameter of S, respectively, and let \u03b1&gt;1 and \u03b2\u22651 be positive, integer-valued parameters. The algorithm for the width problem uses O(\u03b1n) space, supports updates in O(\u03b1 log <jats:sup>2<\/jats:sup> n) time, and reports in O(\u03b1 log <jats:sup>2<\/jats:sup> n) time an approximation, \u0174, to the width such that [Formula: see text]. The algorithm for the diameter problem uses O(\u03b2n) space, supports updates in O(\u03b2 log n) time, and reports in O(\u03b2) time an approximation, [Formula: see text], to the diameter such that [Formula: see text]. Thus, for instance, even for \u03b1 as small as 11, \u0174\/W\u22641.01, and for \u03b2 as small as 9, [Formula: see text]. All bounds stated are worst-case. Both algorithms, but especially the one for the diameter problem, use well-understood data structures and should be simple to implement. The diameter result yields a fast implementation of the greedy heuristic for maximum-weight Euclidean matching and an efficient online algorithm to maintain approximate convex hulls in the plane. <\/jats:p>","DOI":"10.1142\/s021819599300021x","type":"journal-article","created":{"date-parts":[[2004,11,23]],"date-time":"2004-11-23T03:29:30Z","timestamp":1101180570000},"page":"331-344","source":"Crossref","is-referenced-by-count":13,"title":["ON MAINTAINING THE WIDTH AND DIAMETER OF A PLANAR POINT-SET ONLINE"],"prefix":"10.1142","volume":"03","author":[{"given":"RAVI","family":"JANARDAN","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Minnesota, Minneapolis, MN 55455, U.S.A."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S021819599300021X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:31:05Z","timestamp":1565137865000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S021819599300021X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,9]]},"references-count":0,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1993,9]]}},"alternative-id":["10.1142\/S021819599300021X"],"URL":"https:\/\/doi.org\/10.1142\/s021819599300021x","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,9]]}}}