平面格子上の2種点集合の平衡分割問題

• Item type: SIG Technical Reports(1)
• 公開日: 2008-01-23
• タイトル: 平面格子上の2種点集合の平衡分割問題
• タイトル / 言語: en
• タイトル: Balanced Subdivision of Two Sets of Points in the Plane Lattice
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 茨城大学工学部
• 著者所属: 茨城大学工学部
• 著者所属: 茨城大学工学部
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Ibaraki University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Ibaraki University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Ibaraki University
• 著者名: 宇野, 美由紀; 河野, 智治; 加納, 幹雄
• 著者名(英): Miyuki, UNO; Tomoharu, KAWANO; Mikio, KANO
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 平面格子上にある赤点の集合と青点の集合の分割について述べる．最初の定理は，ハム・サンドイッチの定理と類似する次の結果である．平面格子上にある2n個の赤点と2m個の青点に対して，これらを同時に2等分割する準直交分割が存在する．格子上の点集合において，各格子線上に高々1点しかその点がないとき，この点集合は一般の位置にあるという．また，各格子線との共通部分がひとつの直線分かまたは空集合となる連結領域を格子凸領域という．次に，一般の位置にある赤点集合と青点集合は凸領域によって3等分割できることも示す．つまり，平面格子上の一般の位置にある3n個の赤点と3m個の青点は，平面を3個の格子凸領域に分割して，各領域には赤点n個と青点m個が存在するようにできる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2008, 号 6(2008-AL-116), p. 31-38, 発行日 2008-01-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会