{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T09:41:41Z","timestamp":1773567701327,"version":"3.50.1"},"reference-count":0,"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":[[1993,12]]},"abstract":"<jats:p> We study several variations on one basic approach to the task of simplifying a plane polygon or subdivision: Fatten the given object and construct an approximation inside the fattened region. We investigate fattening by convolving the segments or vertices with disks and attempt to approximate objects with the minimum number of line segments, or with near the minimum, by using efficient greedy algorithms. We give some variants that have linear or O(n log n) algorithms approximating polygonal chains of n segments. We also show that approximating subdivisions and approximating with chains with. no self-intersections are NP-hard. <\/jats:p>","DOI":"10.1142\/s0218195993000257","type":"journal-article","created":{"date-parts":[[2004,11,22]],"date-time":"2004-11-22T22:29:30Z","timestamp":1101162570000},"page":"383-415","source":"Crossref","is-referenced-by-count":73,"title":["APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS"],"prefix":"10.1142","volume":"03","author":[{"given":"LEONIDAS J.","family":"GUIBAS","sequence":"first","affiliation":[{"name":"Dept. of Computer Science, Stanford, CA USA 94305, USA"},{"name":"DEC SRC, 130 Lytton Ave, Palo Alto, CA USA 94301, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JOHN E.","family":"HERSHBERGER","sequence":"additional","affiliation":[{"name":"DEC SRC, 130 Lytton Ave, Palo Alto, CA USA 94301, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JOSEPH S.B.","family":"MITCHELL","sequence":"additional","affiliation":[{"name":"Dept. of Applied Math, SUNY, Stony Brook, NY USA 11794\u20133600, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JACK SCOTT","family":"SNOEYINK","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science, UBC, Vancouver, B.C. Canada V6T 1Z2, Canada"}],"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\/S0218195993000257","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:36:41Z","timestamp":1565177801000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195993000257"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,12]]},"references-count":0,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1993,12]]}},"alternative-id":["10.1142\/S0218195993000257"],"URL":"https:\/\/doi.org\/10.1142\/s0218195993000257","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,12]]}}}