Balanced partitions of two sets of points in the plane

被引：22

作者：

Kaneko, A ^{[1
]}

Kano, M

机构：

[1] Kogakuin Univ, Dept Comp Sci & Commun Engn, Shinjuku Ku, Tokyo 1638677, Japan

[2] Ibaraki Univ, Dept Comp & Informat Sci, Hitachi, Ibaraki 3168511, Japan

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 1999年 / 13卷 / 04期

关键词：

balanced partition; point set; plane;

D O I：

10.1016/S0925-7721(99)00024-3

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We prove the following theorem. Let m greater than or equal to 2 and q greater than or equal to 1 be integers and let S and T be two disjoint sets of points in the plane such that no three points of S boolean OR T are on the same line, /S/ = 2q and /T/ = mq. Then S boolean OR T can be partitioned into q disjoint subsets P-1, P-2,..., P-q satisfying the following two conditions: (i) conv(P-i) boolean AND conv(P-j) = phi for all 1 less than or equal to i < j less than or equal to q, where conv(P-i) denotes the convex hull of P-i; and (ii) /P-i boolean AND S/ = 2 and /P-i boolean AND T/ = m for all 1 less than or equal to i less than or equal to q. (C) 1999 Elsevier Science B.V. All rights reserved.

引用

页码：253 / 261

页数：9