QUASI-RANDOM 2-COLORINGS OF POINT SETS

被引：2

作者：

BECK, J ^{[1
]}

机构：

[1] RUTGERS STATE UNIV, DEPT MATH, NEW BRUNSWICK, NJ 08903 USA

来源：

RANDOM STRUCTURES & ALGORITHMS | 1991年 / 2卷 / 03期

关键词：

DISCREPANCY OF HYPERGRAPHS; PERMUTATION; MONOTONE SUBSEQUENCES;

D O I：

10.1002/rsa.3240020304

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Given an arbitrary set of N points on the plane, one can two-color the points red and blue in such a way that the difference of the numbers of red and blue points in any half-plane has absolute value less than N1/4(log N)4. This is essentially best possible.

引用

页码：289 / 302

页数：14

共 11 条

[1] GEOMETRIC METHODS IN THE STUDY OF IRREGULARITIES OF DISTRIBUTION [J].

ALEXANDER, R .

COMBINATORICA, 1990, 10 (02) :115-136

[2]

ALEXANDER R, IN PRESS INVENT MATH

[3] INTEGRAL APPROXIMATION SEQUENCES [J].

BECK, J ;

SPENCER, J .

MATHEMATICAL PROGRAMMING, 1984, 30 (01) :88-98

[4] ON A PROBLEM OF ROTH,K.F. CONCERNING IRREGULARITIES OF POINT DISTRIBUTION [J].

BECK, J .

INVENTIONES MATHEMATICAE, 1983, 74 (03) :477-487

[5] WELL-DISTRIBUTED 2-COLORINGS OF INTEGERS RELATIVE TO LONG ARITHMETIC PROGRESSIONS [J].

BECK, J ;

SPENCER, J .

ACTA ARITHMETICA, 1984, 43 (03) :287-294

[6] BALANCED 2-COLORINGS OF FINITE SETS IN THE SQUARE-I [J].

BECK, J .

COMBINATORICA, 1981, 1 (04) :327-335

[7] ROTH ESTIMATE OF THE DISCREPANCY OF INTEGER SEQUENCES IS NEARLY SHARP [J].

BECK, J .

COMBINATORICA, 1981, 1 (04) :319-325

[8]

BECK J, 1988, DISCRETE MATH, V73, P13

[9]

Erdos P., 1935, COMPOS MATH, V2, P463

[10] BALANCING VECTORS IN THE MAX NORM [J].

SPENCER, J .

COMBINATORICA, 1986, 6 (01) :55-65

← 1 2 →