{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T06:43:39Z","timestamp":1740120219692,"version":"3.37.3"},"reference-count":16,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","funder":[{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["CCF-1422311","CCF-1423615"],"award-info":[{"award-number":["CCF-1422311","CCF-1423615"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2018,6]]},"abstract":"<jats:p> We address the problem of reconstructing a polygon from the multiset of its edges. Given [Formula: see text] line segments in the plane, find a polygon with [Formula: see text] vertices whose edges are these segments, or report that none exists. It is easy to solve the problem in [Formula: see text] time if we seek an arbitrary polygon or a simple polygon. We show that the problem is NP-complete for weakly simple polygons, that is, a polygon whose vertices can be perturbed by at most [Formula: see text], for any [Formula: see text], to obtain a simple polygon. We give [Formula: see text]-time algorithms for reconstructing weakly simple polygons: when all segments are collinear or the segment endpoints are in general position. These results extend to the variant in which the segments are directed. <\/jats:p><jats:p> We study related problems for the case that the union of the [Formula: see text] input segments is connected. (i) If each segment can be subdivided into several segments, find the minimum number of subdivision points to form a weakly simple polygon. (ii) If new line segments can be added, find the minimum total length of new segments that creates a weakly simple polygon. We give worst-case upper and lower bounds for both problems. <\/jats:p>","DOI":"10.1142\/s021819591860004x","type":"journal-article","created":{"date-parts":[[2018,7,12]],"date-time":"2018-07-12T21:58:56Z","timestamp":1531432736000},"page":"161-180","source":"Crossref","is-referenced-by-count":0,"title":["Reconstruction of Weakly Simple Polygons from Their Edges"],"prefix":"10.1142","volume":"28","author":[{"given":"Hugo A.","family":"Akitaya","sequence":"first","affiliation":[{"name":"Department of Computer Science, Tufts University, 161 College Ave., Medford, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[{"name":"Department of Mathematics, California State University Northridge, 18111 Nordhoff St., Los Angeles, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2018,7,12]]},"reference":[{"key":"S021819591860004XBIB001","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9918-3"},{"key":"S021819591860004XBIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.10.026"},{"key":"S021819591860004XBIB005","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574703"},{"key":"S021819591860004XBIB006","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.12.090"},{"key":"S021819591860004XBIB008","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"S021819591860004XBIB009","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195912500045"},{"key":"S021819591860004XBIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2011.04.003"},{"key":"S021819591860004XBIB011","first-page":"225","volume":"40","author":"Formann M.","year":"1990","journal-title":"Bull. EATCS"},{"key":"S021819591860004XBIB012","doi-asserted-by":"publisher","DOI":"10.1007\/BF01442866"},{"key":"S021819591860004XBIB013","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(02)00172-4"},{"key":"S021819591860004XBIB014","doi-asserted-by":"publisher","DOI":"10.1007\/BF01990536"},{"key":"S021819591860004XBIB015","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-70467-2.50013-8"},{"key":"S021819591860004XBIB016","volume-title":"Handbook of Discrete and Computational Geometry","author":"Pach J.","year":"2017","edition":"3"},{"key":"S021819591860004XBIB017","doi-asserted-by":"publisher","DOI":"10.1137\/0218075"},{"key":"S021819591860004XBIB018","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.09.002"},{"key":"S021819591860004XBIB019","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(92)90020-S"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S021819591860004X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,21]],"date-time":"2019-09-21T04:42:51Z","timestamp":1569040971000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S021819591860004X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6]]},"references-count":16,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2018,7,12]]},"published-print":{"date-parts":[[2018,6]]}},"alternative-id":["10.1142\/S021819591860004X"],"URL":"https:\/\/doi.org\/10.1142\/s021819591860004x","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"type":"print","value":"0218-1959"},{"type":"electronic","value":"1793-6357"}],"subject":[],"published":{"date-parts":[[2018,6]]}}}