著者

宇野 美由紀 河野 智治 加納 幹雄

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2008, no.6, pp.31-38, 2008-01-23

---

平面格子上にある赤点の集合と青点の集合の分割について述べる.最初の定理は,ハム・サンドイッチの定理と類似する次の結果である.平面格子上にある2n個の赤点と2m個の青点に対して,これらを同時に2等分割する準直交分割が存在する.格子上の点集合において,各格子線上に高々1点しかその点がないとき,この点集合は一般の位置にあるという.また,各格子線との共通部分がひとつの直線分かまたは空集合となる連結領域を格子凸領域という.次に,一般の位置にある赤点集合と青点集合は凸領域によって3等分割できることも示す.つまり,平面格子上の一般の位置にある3n個の赤点と3m個の青点は,平面を3個の格子凸領域に分割して,各領域には赤点n個と青点m個が存在するようにできる.We consider balanced subdivision of red points and blue points in the plane lattice. We first show that if 2n red points and 2m blue points are given in the plane lattice, then there exists a semi-rectangular that bisects both red points and blue points. A set S of points in the plance lattices is said to be in general position if every lattice line contains at most one point of S. For a connected region of the lattice, if the intersection of every lattice line and the region is empty or consists of one line segment, then the region is called a lattice convex set. We next show that if 3n red points and 3m blue points are given in the plane lattice in general position, then the plance can be patitioned into three lattice convex regions so that each region contains exactly m red points and n blue points.