{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,12]],"date-time":"2026-08-12T04:00:07Z","timestamp":1786507207369,"version":"3.56.0"},"reference-count":14,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1998,8]]},"abstract":"<jats:p>A new polygon decomposition problem, the anchored area partition problem, which has applications to a multiple-robot terrain-covering problem is presented. This problem concerns dividing a given polygon P into n polygonal pieces, each of a specified area and each containing a certain point (site) on its boundary or in its interior. First the algorithm for the case when P is convex and contains no holes is presented. Then the generalized version that handles nonconvex and nonsimply connected polygons is presented. The algorithm uses sweep-line and divide-and-conquer techniques to construct the polygon partition. The input polygon P is assumed to have been divided into a set of p convex pieces (p = 1 when P is convex), which can be done in O(v<jats:sub>P<\/jats:sub>log log v<jats:sub>P<\/jats:sub>) time, where v<jats:sub>P<\/jats:sub>is the number of vertices of P and p = O(v<jats:sub>P<\/jats:sub>), using algorithms presented elsewhere in the literature. Assuming this convex decomposition, the running time of the algorithm presented here is O(pn<jats:sup>2<\/jats:sup>+vn), where v is the sum of the number of vertices of the convex pieces.<\/jats:p>","DOI":"10.1142\/s0218195998000230","type":"journal-article","created":{"date-parts":[[2003,7,22]],"date-time":"2003-07-22T11:10:21Z","timestamp":1058872221000},"page":"437-466","source":"Crossref","is-referenced-by-count":70,"title":["Polygon Area Decomposition for Multiple-Robot Workspace Division"],"prefix":"10.1142","volume":"08","author":[{"given":"Susan","family":"Hert","sequence":"first","affiliation":[{"name":"Computer Sciences Department, University of Wisconsin, 1210 West Dayton Street, Madison, Wisconsin 53706-1685, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vladimir","family":"Lumelsky","sequence":"additional","affiliation":[{"name":"Robotics Laboratory, University of Wisconsin, 1513 University Avenue, Madison, Wisconsin 53706, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01553882"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187904"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01933206"},{"issue":"91","key":"p_16","first-page":"119","volume":"3","author":"Hert S.","year":"1996","journal-title":"Journal of Autonomous Robots"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187834"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1137\/0214056"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.4.4.435"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130308"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.1109\/70.59357"},{"key":"p_28","doi-asserted-by":"publisher","DOI":"10.1109\/JRA.1987.1087133"},{"key":"p_30","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056648"},{"issue":"3","key":"p_31","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1080\/00150517.1992.12429353","volume":"30","author":"Page W","year":"1992","journal-title":"Fibonacci Quarterly"},{"key":"p_32","doi-asserted-by":"publisher","DOI":"10.1109\/21.61213"},{"key":"p_34","doi-asserted-by":"publisher","DOI":"10.1145\/357346.357348"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195998000230","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,13]],"date-time":"2024-12-13T07:17:41Z","timestamp":1734074261000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195998000230"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,8]]},"references-count":14,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1998,8]]}},"alternative-id":["10.1142\/S0218195998000230"],"URL":"https:\/\/doi.org\/10.1142\/s0218195998000230","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,8]]}}}