Weight-equitable subdivision of red and blue points in the plane
Weight-equitable subdivision of red and blue points in the plane
复制标题
平面中红点和蓝点的重量均衡细分
DOI：
10.1142/s0218195918500024
复制
发表时间：
2018
影响因子：
--
通讯作者：
Jude Buot and Mikio Kano
中科院分区：
文献类型：
--
作者：
Yusuke Yoshida;Yoshio Yamada;Jude Buot and Mikio Kano
设和为两个不相交的红点和蓝点的集合，分别位于平面的一般位置。为每个红点和蓝点分别赋予一个权重，其中和为正整数。将平面上一个区域的权定义为其中红点和蓝点的权之和，给出了当总权为某整数时，存在平分平面权的直线的充要条件.此外，我们密切关注的特殊情况下，因为这种情况是重要的，以产生一个重量公平的细分的平面。在其他结果中，我们证明了对于任意的具有全权的构形，对于某个整数和奇数，平面可以被细分为权的凸区域，且仅当。利用主要结果的证明，我们还给出了在平面上求权均衡剖分的多项式时间算法。
Letandbe two disjoint sets of red points and blue points, respectively, in the plane in general position. Assign a weightto each red point and a weightto each blue point, whereandare positive integers. Define the weight of a region in the plane as the sum of the weights of red and blue points in it. We give necessary and sufficient conditions for the existence of a line that bisects the weight of the plane whenever the total weightis, for some integer. Moreover, we look closely into the special case whereandsince this case is important to generate a weight-equitable subdivision of the plane. Among other results, we show that for any configuration ofwith total weight, for some integerand odd integer, the plane can be subdivided intoconvex regions of weightif and only if. Using the proofs of the main result, we also give a polynomial time algorithm in finding a weight-equitable subdivision in the plane.