Information Technology Reference
In-Depth Information
r
1
r
k
q
l
r
k
d
1
P
c
d
2
P
a
r
k
+1
r
k
+1
d
2
q
j
+2
q
j
+1
r
k
+2
q
j
+1
d
2
P
d
q
j
P
b
r
m
q
1
q
j
(a)
(b)
Fig. 6.
(a) Sets
P
a
,
P
b
,
P
c
,and
P
d
at a certain time instant during the rotation of
d
2
. (b) The slope
of
d
2
with respect to the slopes of the lines orthogonal to
q
j
q
j
+1
,to
q
j
+1
q
j
+2
,to
r
k
r
k
+1
,andto
r
k
+1
r
k
+2
.
P
b
=
P
1
(
d
1
)
P
2
(
d
2
).Note
that every point in
P
is contained in one of
P
a
,
P
b
,
P
c
,and
P
d
.A(
d
1
,
d
2
)
-partition
of
P
is
balanced
if
∩
P
2
(
d
2
),
P
c
=
P
2
(
d
1
)
∩
P
1
(
d
2
),and
P
d
=
P
2
(
d
1
)
∩
P
c
|≤
|P|
2
+1.Wenowargue
that, for every point set
P
, a balanced (
d
1
,
d
2
)-partition of
P
always exists, even if
d
1
is arbitrarily prescribed.
P
d
|≤
|P|
2
|
P
a
|
|
|
P
b
|
|
+
+1and
+
Lemma 5.
Let
P
be a convex pointsetandlet
d
1
be a directed straightline not or-
thogonaltoany linethrough two points of
P
.Then,there exists a directed straightline
d
2
thatisnot orthogonaltoany linethrough two points of
P
such thatthe
(
d
1
,
d
2
)
-
partition of
P
is balanced.
Proof.
Denote by
q
1
=
p
a
(
d
1
)
,q
2
,...,q
l
,q
l
+1
=
p
b
(
d
1
) the points of
P
encoun-
tered when clockwise walking on the boundary of
H
P
from
p
a
(
d
1
) to
p
b
(
d
1
).Also,
denote by
r
1
=
p
b
(
d
1
)
,r
2
,...,r
m
,r
m
+1
=
p
a
(
d
1
) the points of
P
encountered when
clockwise walking on the boundary of
H
P
from
p
b
(
d
1
) to
p
a
(
d
1
).
Initialize
d
2
to be a directed straight line coincident with
d
1
.When
d
2
=
d
1
,we
have
P
a
=
{
q
1
,q
2
,...,q
l
}
,
P
d
=
{
r
1
,r
2
,...,r
m
}
,
P
b
=
∅
,and
P
c
=
∅
.Wenow
clockwise rotate
d
2
until it is opposite to
d
1
(that is, parallel and pointing in the op-
posite direction). As we rotate
d
2
,sets
P
1
(
d
2
) and
P
2
(
d
2
) change, hence sets
P
a
,
P
b
,
P
c
,and
P
d
change as well. When
d
2
is opposite to
d
1
,wehave
P
a
=
∅
,
P
d
=
∅
,
P
b
=
{q
1
,q
2
,...,q
l
}
. We will argue that there is a mo-
ment during such a rotation of
d
2
in which the corresponding (
d
1
,
d
2
)-partition of
P
is
balanced. Assume that at any time instant during the rotation of
d
2
the following hold
(see Figs. 6(a)-(b)):
,and
P
c
=
{r
1
,r
2
,...,r
m
}
-
P
b
=
(possibly
P
b
is empty);
-
P
a
=
{q
j
+1
,q
j
+2
,...,q
l
}
{
q
1
,q
2
,...,q
j
}
(possibly
P
a
is empty);
-
P
c
=
{
r
1
,r
2
,...,r
k
}
(possibly
P
c
is empty);
-
P
d
=
(possibly
P
d
is empty); and
-
q
j
+1
and
r
k
+1
are the minimum and maximum point of
P
w.r.t.
d
2
, respectively.
{
r
k
+1
,r
k
+2
,...,r
m
}
The assumption is indeed truewhen
d
2
starts moving, with
j
=0and
k
=0.
