{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T10:48:42Z","timestamp":1769078922685,"version":"3.49.0"},"reference-count":6,"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":[[2005,6]]},"abstract":"<jats:p> Let m be a positive integer and let R<jats:sub>1<\/jats:sub>, R<jats:sub>2<\/jats:sub> and B be three disjoint sets of points in the plane such that no three points of R<jats:sub>1<\/jats:sub> \u222a R<jats:sub>2<\/jats:sub> \u222a B lie on the same line and |B| = (m-1)|R<jats:sub>1<\/jats:sub>|+m|R<jats:sub>2<\/jats:sub>|. Put g = |R<jats:sub>1<\/jats:sub>\u222aR<jats:sub>2<\/jats:sub>|. Then there exists a subdivision X<jats:sub>1<\/jats:sub>\u222aX<jats:sub>2<\/jats:sub>\u222a\u22ef\u222aX<jats:sub>g<\/jats:sub> of the plane into g disjoint convex polygons such that (i) |X<jats:sub>i<\/jats:sub> \u2229 (R<jats:sub>1<\/jats:sub> \u222a R<jats:sub>2<\/jats:sub>)| = 1 for all 1 \u2264 i \u2264 g; and (ii) |X<jats:sub>i<\/jats:sub>\u2229B| = m-1 if |X<jats:sub>i<\/jats:sub>\u2229R<jats:sub>1<\/jats:sub>| = 1, and |X<jats:sub>i<\/jats:sub>\u2229B| = m if |X<jats:sub>i<\/jats:sub>\u2229R<jats:sub>2<\/jats:sub>| = 1. This partition is called a semi-balanced partition, and our proof gives an O(n<jats:sup>4<\/jats:sup>) time algorithm for finding the above semi-balanced partition, where n = |R<jats:sub>1<\/jats:sub>| + |R<jats:sub>2<\/jats:sub>| + |B|. <\/jats:p><jats:p> We next apply the above result to the following theorem: Let T<jats:sub>1<\/jats:sub>,\u2026,T<jats:sub>g<\/jats:sub> be g disjoint rooted trees such that |T<jats:sub>i<\/jats:sub>| \u2208 {m,m+1} and v<jats:sub>i<\/jats:sub> is the root of T<jats:sub>i<\/jats:sub> for all 1 \u2264 i \u2264 g. Let P be a set of |T<jats:sub>1<\/jats:sub>|+\u22ef+|T<jats:sub>g<\/jats:sub>| points in the plane in general position that contains g specified points p<jats:sub>1<\/jats:sub>,\u2026,p<jats:sub>g<\/jats:sub>. Then the rooted forest T<jats:sub>1<\/jats:sub> \u222a \u22ef \u222a T<jats:sub>g<\/jats:sub> can be straight-line embedded onto P so that each v<jats:sub>i<\/jats:sub> corresponds to p<jats:sub>i<\/jats:sub> for every 1 \u2264 i \u2264 g. <\/jats:p>","DOI":"10.1142\/s0218195905001671","type":"journal-article","created":{"date-parts":[[2005,7,5]],"date-time":"2005-07-05T14:52:13Z","timestamp":1120575133000},"page":"229-238","source":"Crossref","is-referenced-by-count":14,"title":["SEMI-BALANCED PARTITIONS OF TWO SETS OF POINTS AND EMBEDDINGS OF ROOTED FORESTS"],"prefix":"10.1142","volume":"15","author":[{"given":"ATSUSHI","family":"KANEKO","sequence":"first","affiliation":[{"name":"Saitama, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MIKIO","family":"KANO","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Sciences, Ibaraki University, Hitachi, Ibaraki, 316-8511, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"crossref","unstructured":"P.\u00a0Bose, M.\u00a0McAllister and J.\u00a0Snoeyink, Proc. Graph Drawing (GD'95), Lecture Notes in Comp. Science\u00a01190 (Springer Verlag, 1995)\u00a0pp. 64\u201375.","DOI":"10.1007\/BFb0021791"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573994"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009441"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00191-2"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55566-4_25"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00201-7"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195905001671","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:29:28Z","timestamp":1565137768000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195905001671"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":6,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,6]]}},"alternative-id":["10.1142\/S0218195905001671"],"URL":"https:\/\/doi.org\/10.1142\/s0218195905001671","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6]]}}}