Balanced In e als o Two Se s o Poin s on a line o ci cle
A sushi Kaneko aand M. Kano b
aDepa men o Compu e Science and Communica ion Enginee ing
Kogakuin Uni e si y, Nishi-Shinjuku, Shinjuku-ku, Tokyo, 163-8677, Japan
bDepa men o Compu e and In o ma ion Sciences
Iba aki Uni e si y, Hi achi, Iba aki, 316-8511, Japan
[email p o ec ed]a aki.ac.jp h p://go ogo o.cis.iba aki.ac.jp
Abs ac
Le n, m, k, h be posi i e in ege s such ha 1 ≤n≤m, 1 ≤k≤nand 1 ≤h≤m. Then we gi e a necessa y
and su icien condi ion o e e y con igu a ion wi h n ed poin s and mblue poin s on a line o ci cle o ha e an
in e al con aining p ecisely k ed poin s and hblue poin s.
Key wo ds: balanced in e al, in e al, wo se s o poin s, line, ci cle
1. A balanced in e al on a line
In his sec ion we shall p o e he ollowing he-
o em.
Theo em 1 Le n, m, k, h be in ege s such ha
1≤n≤m,1≤k≤nand 1≤h≤m. Then
o any n ed poin s and mblue poin s on a line
in gene al posi ion (i.e., no wo poin s lie on he
same posi ion.), he e exis s an in e al ha con-
ains p ecisely k ed poin s and hblue poin s i and
only i
j n
k+ 1k+ 1(h−1) < m < j n
k−1k(h+ 1),
(1)
whe e he igh mos e m is an in ini e numbe
when k= 1.
We begin wi h an example o ou heo em. Con-
side a con igu a ion consis ing o 10 ed poin s and
20 blue poin s on a line in gene al posi ion. Then
by he abo e heo em, we can easily show ha i
k∈ {1,2,3,5,10}, hen such a con igu a ion has
an in e al con aining exac ly k ed poin s and 2k
blue poin s; o he wise (i.e., k∈ {4,6,7,8,9}) he e
exis a con igu a ion ha has no such an in e al
(Fig. 1). We call an in e al ha con ains gi en
numbe o ed poin s and blue poin s a balanced
in e al.
(a):
(b):
Red poin s =
Blue poin s =
Fig. 1. (a): An in e al con aining 3 ed poin s and 6 blue
poin s; (b): A con igu a ion ha has no in e al con aining
exac ly 4 ed poin s and 8 blue poin s.
Theo em 1 is an easy consequence o he ollow-
ing i e lemmas.
Fo a con igu a ion wi h ed and blue poin s on
a line, we deno e by Rand B he se s o ed poin s
and blue poin s, espec i ely. A con igu a ion X
wi h n ed poin s and mblue poin s on he line is
exp essed as
{x1} ∪ {x2} ∪ · · · ∪ {xn+m},
20 h EWCG Se ille, Spain (2004)
20 h Eu opean Wo kshop on Compu a ional Geome y
whe e each xideno es a ed poin o a blue poin
o de ed om le o igh . The con igu a ion Xis
also exp essed as
R(1) ∪B(1) ∪ · · · ∪ R(s)∪B(s),
whe e R(i) and B(i) deno e disjoin subse s o R
and B, espec i ely, and some o hem may be
emp y se s. Fo a se Y, we deno e by |Y| he ca -
dinali y o Y.
Lemma 2 I
m≤j n
k+ 1k+ 1(h−1),(2)
hen he e exis s a con igu a ion wi h n ed poin s
and mblue poin s ha has no in e al con aining
exac ly k ed poin s and hblue poin s.
PROOF. Le =⌊n
k−1⌋. Then n≤( +1)(k−1),
and m≥ (h+ 1) by (4). Hence we can ob ain he
ollowing con igu a ion wi h n ed poin s and m
blue poin s:
R(1) ∪B(1) ∪ · · · ∪ R( + 1) ∪B( + 1),
whe e |R(i)| ≤ k−1 o e e y 1 ≤i≤ +1, |R(1)∪
· · ·∪R( +1)|=n,|B(i)|=h+1 o e e y 1 ≤i≤
,|B( + 1)|=m−(h+ 1) ≥0 and |B(1) ∪ · · · ∪
B( + 1)|=m. Then his con igu a ion ob iously
has no in e al con aining exac ly k ed poin s and
hblue poin s since e e y in e al con aining k ed
poin s mus include B(j) o some 1 ≤j≤ .
Lemma 3 I
m > j n
k+ 1k+ 1(h−1),(3)
hen e e y con igu a ion wi h n ed poin s and m
blue poin s on a line has an in e al con aining ex-
ac ly k ed poin s and a leas hblue poin s.
PROOF. Le =⌊n
k+1 ⌋. Le Xbe a con igu a ion
wi h n ed poin s and mblue poin s. Suppose ha
Xhas no desi ed in e al. Namely, we assume ha
e e y in e al con aining exac ly k ed poin s has
a mos h−1 blue poin s.
Le 1, 2,··· , nbe he ed poin s o Xo -
de ed om le o igh . Fo in ege s 1 ≤i <
j≤n, le I(i, j) deno e an open in e al ( i, j),
and le B(i, j) deno e he se o blue poin s con-
ained in I(i, j). Fu he mo e, B(−∞, i) deno es
he se o blue poin s con ained in he open in e al
(−∞, i), and B(i, ∞) is de ined analogously. Then
o any in ege 1 ≤s≤ −1, I(s(k+1),(s+1)(k+
1)) con ains exac ly k ed poin s { j|s(k+1)+1 ≤
j≤(s+1)(k+1)−1)}, and hus |B(s(k+1),(s+
1)(k+ 1))| ≤ h−1 by ou assump ion. Simila ly,
an open in e al (−∞, k+1) con ains exac ly k ed
poin s, and hus |B(−∞, k + 1)| ≤ h−1. Mo e-
o e , since n < ( + 1)(k+ 1), I( (k+ 1),∞) has a
mos k ed poin s, and hus B( (k+1),∞)≤h−1.
The e o e
|B| ≤ |B(−∞, k + 1) ∪B(k+ 1,2(k+ 1)) ∪ · · ·
∪B( (k+ 1),∞)|
≤( + 1)(h−1).
This con adic s (3). Consequen ly he lemma is
p o ed.
Lemma 4 I 2≤kand
m≥jn
k−1k(h+ 1),(4)
hen he e exis s a con igu a ion wi h n ed poin s
and mblue poin s on a line ha has no in e al
con aining exac ly k ed poin s and hblue poin s.
PROOF. Le =⌊n
k−1⌋. Then n≤( +1)(k−1),
and m≥ (h+ 1) by (4). Hence we can ob ain he
ollowing con igu a ion wi h n ed poin s and m
blue poin s:
R(1) ∪B(1) ∪ · · · ∪ R( + 1) ∪B( + 1),
whe e |R(i)| ≤ k−1 o e e y 1 ≤i≤ +1, |R(1)∪
· · ·∪R( +1)|=n,|B(i)|=h+1 o e e y 1 ≤i≤
,|B( + 1)|=m−(h+ 1) ≥0 and |B(1) ∪ · · · ∪
B( + 1)|=m. Then his con igu a ion ob iously
has no in e al con aining exac ly k ed poin s and
hblue poin s since e e y in e al con aining k ed
poin s mus include B(j) o some 1 ≤j≤ .
Lemma 5 I 2≤kand
m < jn
k−1k(h+ 1),(5)
hen e e y con igu a ion wi h n ed poin s and m
blue poin s on a line has an in e al con aining ex-
ac ly k ed poin s and a mos hblue poin s.
PROOF. Le =⌊n
k−1⌋. Le Xbe a con igu a-
ion wi h n ed poin s and mblue poin s. Suppose
ha Xhas no desi ed in e al. Namely, we assume
Ma ch 25-26, 2004 Se ille (Spain)
ha e e y in e al con aining exac ly k ed poin s
has a leas h+ 1 blue poin s.
Le 1, 2,··· , nbe he ed poin s o Xo de ed
om le o igh . Fo in ege s 1 ≤i < j ≤n,
le I[i, j], deno e a closed in e al [ i, j], and le
B′(i, j) deno e he se o blue poin s con ained in
I[i, j].
Then o any in ege 0 ≤s≤ −2, I[k+s(k−
1), k + (s+ 1)(k−1)] con ains exa ly k ed poin s
{ j|k+s(k−1) ≤j≤k+ (s+ 1)(k−1))}, and
hus |B′(k+s(k−1), k + (s+ 1)(k−1))| ≥ h+ 1
by ou assump ion. Simila ly, we ha e |B′(1, k)| ≥
h+ 1. The e o e
|B| ≥ |B′(1, k)∪B′(k, k + (k−1)) ∪ · · ·
∪B′(k+ ( −2)(k−1), k + ( −1)(k−1))|
≥ (h+ 1).
This con adic s (5). Consequen ly he lemma is
p o ed.
Lemma 6 Conside a con igu a ion wi h n ed
poin s and mblue poin s on a line. Suppose ha
he e exis s wo in e als Iand Jsuch ha bo h I
and Jcon ain exac ly k ed poin s espec i ely, I
con ains a mos hblue poin s, and ha Jcon ains
a leas hblue poin s. Then he e exis s an in e al
ha con ains exac ly k ed poin s and hblue poin s.
PROOF. I he se s o ed poin s con ained in I
and J, espec i ely, a e he same, hen he lemma
immedia ely ollows. Thus we may assume ha I∩
R6=J∩R, whe e Rdeno e he se o n ed poin s.
Wi hou loss o gene ali y, we may assume ha he
le mos ed poin o Ilies o he le o J.
We shall show ha we can mo e I o Js ep by
s ep in such a way ha he numbe o ed poin s is
a cons an kand he numbe o blue poin s changes
±1 a each s ep. We i s emo e he blue poin s
le o he le mos ed poin o Ione by one, and
hen add he consecu i e blue poin s lying o he
igh o Ione by one, and deno e he esul ing in-
e al by I1(Fig. 3). We nex simul aneously e-
mo e he le mos ed poin o I1and add he ed
poin lying o he igh o I1, and ge an in e al I2,
which also con ains exac ly k ed poin s and whose
blue poin s a e he same as hose in I1(Fig. 3). By
epea ing his p ocedu e, we can ge an in e al
whose ed poin se is equal o ha o J. The e-
o e, we can mo e I o Jin he desi ed way. Con-
sequen ly, we can ind he equi ed in e al, which
con ains exac ly k ed poin s and hblue poin s.
2. A balanced in e al on a ci cle
(a)
(b)
Red poin s =
Blue poin s =
Fig. 2. (a): An in e al con aining 4 ed poin s and 8 blue
poin s; (b): A con igu a ion ha has no in e al con aining
exac ly 4 ed poin s and 5 blue poin s.
In his sec ion, we conside he ollowing heo-
em, and gi e i s example in Figu e e ig:2
Theo em 7 Le n, m, k, h be in ege s such ha
1≤n≤m,1≤k≤nand 1≤h≤m. Then
o any n ed poin s and mblue poin s on a ci cle
in gene al posi ion (i.e., no wo poin s lie on he
same posi ion.), he e exis s an in e al ha con-
20 h Eu opean Wo kshop on Compu a ional Geome y
ains p ecisely k ed poin s and hblue poin s i and
only i
n
k+ 1(h−1) < m < n
k−1(h+ 1),(6)
whe e he igh mos e m is an in ini e numbe
when k= 1.
Theo em 8 can be p o ed by showing simila
lemmas as in he case o line. We conclude he
pape by he nex conjec u e.
Conjec u e 8 Le n, m, k, h be in ege s such ha
1≤n≤m,1≤k≤nand 1≤h≤m. Then
o any n ed poin s and mblue poin s in he plane
in gene al posi ion (i.e., no h ee poin s lie on he
same.), he e exis s a wedge ha con ains p ecisely
k ed poin s and hblue poin s i and only i
n
k+ 2(h−1) < m < n
k−2(h+ 1),(7)
whe e he igh mos e m is an in ini e numbe
when k= 1.
P
1
2
P
(a)
(b)
1
2
Fig. 3. Wedges con aining 4 ed poin s and 8 blue poin s.
Re e ences
[1] B´a ´any, I., and Ma ouˇsek, J.; Simul aneous pa i ions
o measu es by k- ans, Disc e e Compu . Geom. 25
(2001)317–334.
[2] Goodman, J. and O’Rou ke, J.; Handbook o Disc e e
and Compu a ional Geome y, CRC P ess, (1997) .
[3] Kaneko, A. and Kano, M.; Disc e e geome y on ed
and blue poin s in he plane — A su ey, Disc e e
and Compu a ional Geome y・The Goodman-Pollack
Fes sch i ・Wi h con ibu ions by nume ous expe s
(Sp inge ) (2003) 551-570.