平面上の点集合の平衡分割問題

• Item type: SIG Technical Reports(1)
• 公開日: 1998-07-22
• タイトル: 平面上の点集合の平衡分割問題
• タイトル / 言語: en
• タイトル: Balanced partitions of two sets of points in the plane
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 茨城大学
• 著者所属: 工学院大学
• 著者所属(英): en
• 著者所属(英): Ibaraki University
• 著者所属(英): en
• 著者所属(英): Kogakuin University
• 著者名: 加納幹雄; 金子, 篤司
• 著者名(英): M., Kano; Atsushi, Kaneko
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 平面上にmq個の白点集合Sとnq個の赤点集合Tがあり、S∪Tのどの3点も同一直線上にはないものとする。すると、S∪Tを下記の2つの条件を満たすようなq個の集合P_1，P_2，・・・，Pに分割できるという予想を与え、これがn＝1のとき成り立つことを示したが、今回はn＝2のときにもこの予想が成り立つことを証明する。またその証明から、所望の分割を得るO（N^2logN）のアルゴリズムもえられる、ただしN＝mp＋npである。（1）すべてのの1〓i〓j〓qに対して、conv （P_i）∩conv （P_j）＝φである。（2）すべての1〓i〓qに対して、｜P_i∩S｜＝n and｜P_i∩T｜＝mがなりたつ。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We prove the following theorem: Let n=1,m〓2 and q〓1 be integers and let S and T be two disjoint sets of points in the plane such that no three points of S∪T are on the same line, ｜S｜= nq and ｜T｜= mq. Then S∪T can be partitioned into q disjoint subsets P_1, P_2,…, P_9 satisfying the following two conditions: (i) conv (P_i) ∩conv (P_j)=φ for all 1〓i〓j〓q; and (ii) ｜P_i∩S｜= n and ｜P_i∩T｜=m for all 1〓i〓q. We can obtain an O (NlogN) time algorithm for finding the above desired partition by our proof, where N = mq + nq. We also proved that the above theorem holds for n = 1, and give a conjecture which says that the above theorem holds for all integer n〓3. We don't give a complete proof of this theorem because of lack of pages, and a complete proof can be seen in [3].
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1998, 号 62(1998-AL-063), p. 9-16, 発行日 1998-07-22
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会