{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:47Z","timestamp":1759638287198},"reference-count":6,"publisher":"World Scientific Pub Co Pte Lt","issue":"02n03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2006,6]]},"abstract":"<jats:p> We present approximation algorithms for cutting out a polygon P with n vertices from another convex polygon Q with m vertices by line cuts and ray cuts. For line cuts we require both P and Q are convex while for ray cuts we require Q is convex and P is ray cuttable. Our results answer a number of open problems and are either the first solutions or significantly improve over previously known solutions. For the line cutting version, we prove a key property that leads to a simple, constant factor approximation algorithm. For the ray cutting version, we prove it is possible to compute in almost linear time a cutting sequence that is an O( log <jats:sup>2<\/jats:sup> n)-factor approximation of an optimal cutting sequence. No algorithms were previously known for the ray cutting version. <\/jats:p>","DOI":"10.1142\/s0218195906002014","type":"journal-article","created":{"date-parts":[[2006,4,27]],"date-time":"2006-04-27T12:53:13Z","timestamp":1146142393000},"page":"227-248","source":"Crossref","is-referenced-by-count":11,"title":["CUTTING OUT POLYGONS WITH LINES AND RAYS"],"prefix":"10.1142","volume":"16","author":[{"given":"OVIDIU","family":"DAESCU","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Texas at Dallas, Richardson, TX 75080, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JUN","family":"LUO","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Texas at Dallas, Richardson, TX 75080, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)00160-X"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00036-0"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.01.010"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840360"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(02)00131-1"},{"key":"rf7","first-page":"481","volume":"24","author":"Path J.","journal-title":"Disc. & Comput. Geom."}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195906002014","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:20:36Z","timestamp":1565191236000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195906002014"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6]]},"references-count":6,"journal-issue":{"issue":"02n03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2006,6]]}},"alternative-id":["10.1142\/S0218195906002014"],"URL":"https:\/\/doi.org\/10.1142\/s0218195906002014","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,6]]}}}