权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

BALANCED PARTITIONS OF TWO SETS OF POINTS IN THE PLANE

平面上两组点的平衡划分

基本信息

批准号：
15540137
负责人：
KANO Mikio
金额：
$ 1.73万
依托单位：
IBARAKI UNIVERSITY (2004)Kogakuin University (2003)
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2004
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-15540137/
关键词：
Balanced Partition Balanced subdivision Red and blue points Geometric graph Discrete geometry グラフ離散幾何学平面 2種点集合交差

项目摘要

Recently, the Ham-sandwich Theorem was generalized as follows : If|R|=ag and|B|=bg, then there exists a subdivision X_1∪X_2∪・・・∪X_g of the plane into g disjoint convex polygons such that every X_i contains exactly a red points and b blue points. This theorem was proved by A. Kano and M.Kano for a=1,2 and they proposed it as a conjecture, and then this conjecture was independently proved by three papers.We obtain the following three new results.(1)Suppose that $R$ is a disjoint union of R_1 and R_2. Let|R_1|=g_1 and|R_2|=g_2. If|B|=(m-1)g_1+ mg_2, then we can subdivide the plane into g_1+g_2 disjoint convex polygons X_1∪・・・X_{g_1}∪Y_1∪・・・∪Y_{g_2} so that every X_i contains exactly one red point of R_1 and m-1 blue points, and every Y_j contains exactly one red point of R_2 and m blue points.(2)Let a≧1, g≧0 and h≧0 be integers such that g+h≧1. If|R|=ag+(a+1)h and|B|=(a+1)g+ah, then there exists a subdivision X_1∪・・・∪X_g∪Y_1∪・・・∪ Y_h of the plane into g+h disjoint convex polygons such that every X_i contains exactly a red points and a+1 blue points and every Y_j contains exactly a+1 red points and a blue points.(3)If|R|=a(g_1+g_2)+(a+1)g_3 and|B|=bg_1+(b+1)(g_2+g_3), then there exists a subdivision X_1∪・・・∪X_{g_1}∪Y_1∪・・・∪ Y_{g_2}∪Z_{1}∪・・・∪Z_{g_3} of the plane into g_1+g_2+g_3 disjoint convex polygons such that every X_i contains exactly a red points and b blue points, every Y_i, if any, contains exactly a red points and b+1 blue points, and every Z_i, if any, contains exactly a+1 red points and b+1 blue pointsWe also study some problems on discrete geometry and graph theory related to the above problems.

最近，Ham-sandwich定理被推广如下：如果|R| =ag和|B| =bg，则存在平面的一个细分X_1 <$X_2 <$··<$X_g为g个不相交的凸多边形，使得每个X_i恰好包含a个红点和B个蓝点。这个定理是由A. Kano和M.Kano对a= 1，2提出了一个猜想，然后这个猜想被三篇论文独立地证明了，我们得到了以下三个新结果。（1）设$R$是R_1和R_2的不交并。让|R_1| =g_1，|R_2| =g_2。如果|B| =（m-1）g_1+ mg_2，则可将平面细分为g_1+g_2个不相交的凸多边形X_1 <$···X_{g_1}<$Y_1 <$··<$Y_{g_2}，使得每个X_i恰好包含R_1中的一个红点和m-1个蓝点，每个Y_j恰好包含R_2中的一个红点和m个蓝点。（2）设a ≥ 1，g ≥ 0和h ≥ 0为整数，使得g+h ≥ 1。如果|R| =ag+（a+1）h和|B| =（a+1）g+ah，则存在平面的一个剖分X_1 <$··<$X_g <$Y_1 <$··<$Y_h为g+h个不相交凸多边形，使得每个X_i恰好包含一个红点和一个+1个蓝点，每个Y_j恰好包含一个+1个红点和一个蓝点。(3)If|=a（g_1+g_2）+（a+1）g_3且|B| =bg_1+（B+1）（g_2+g_3），则存在平面的一个剖分X_1 <$··<$X_{g_1}<$Y_1 $>··<$Y_{g_2}<$Z_{1}<$··<$Z_{g_3}为g_1+g_2+g_3个不相交凸多边形，使得每个X_i恰好包含a个红点和B个蓝点，每个Y_i（如果有的话）恰好包含a个红点和B+1个蓝点，并且每个Z_i，|如果有的话，恰好包含a+1个红点和B+1个蓝点.本文还研究了与上述问题有关的离散几何和图论中的一些问题. if any, contains exactly a+1 red points and b+1 blue pointsWe also study some problems on discrete geometry and graph theory related to the above problems.