Information Technology Reference
In-Depth Information
As we keep on clockwise rotating
d
2
, at a certain moment
d
2
becomes orthogonal
to
q
j
+1
q
j
+2
or to
r
k
+1
r
k
+2
(or to both if
q
j
+1
q
j
+2
and
r
k
+1
r
k
+2
are parallel). Thus,
as we keep on clockwise rotating
d
2
,sets
P
a
,
P
b
,
P
c
,and
P
d
change. Namely:
If
d
2
becomes orthogonal first to
q
j
+1
q
j
+2
and then to
r
k
+1
r
k
+2
,thenas
d
2
rotates
clockwise after the position in which it is orthogonal to
q
j
+1
q
j
+2
,wehave
-
P
b
=
{
q
1
,q
2
,...,q
j
,q
j
+1
}
;
-
P
a
=
{
q
j
+2
,q
j
+3
,...,q
l
}
(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
+2
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
}
If
d
2
becomes orthogonal first to
r
k
+1
r
k
+2
andthento
q
j
+1
q
j
+2
,thenas
d
2
rotates
clockwise after the position in which it is orthogonal to
r
k
+1
r
k
+2
,wehavethat
P
a
and
P
b
stay unchanged, that
r
k
+1
passes from
P
d
to
P
c
,andthat
q
j
+1
and
r
k
+2
are the
minimum and maximum point of
P
w.r.t.
d
2
, respectively.
If
d
2
becomes orthogonal to
q
j
+1
q
j
+2
and
r
k
+1
r
k
+2
simultaneously, then as
d
2
rotates clockwise after the position in which it is orthogonal to
q
j
+1
q
j
+2
,wehavethat
q
j
+1
passes from
P
a
to
P
b
,that
r
k
+1
passes from
P
d
to
P
c
,andthat
q
j
+2
and
r
k
+2
are
the minimum and maximum point of
P
w.r.t.
d
2
, respectively.
Observe that:
1. whenever sets
P
a
,
P
b
,
P
c
,and
P
d
change, we have that
|
P
a
|
+
|
P
d
|
and
|
P
b
|
+
|
P
c
|
changeatmostbytwo;
2. when
d
2
starts rotating we have that
|
P
a
|
|
P
d
|
|
P
|
,andwhen
d
2
stops rotating
+
=
|P
a
|
+
|P
d
|
=0;
3. when
d
2
starts rotating we have that
we have that
|
P
b
|
+
|
P
c
|
=0,andwhen
d
2
stops rotating
we have that
|
P
b
|
+
|
P
c
|
=
|
P
|
;and
4.
|
P
a
|
+
|
P
b
|
+
|
P
c
|
+
|
P
d
|
=
|
P
|
holds at any time instant.
By continuity, there is a time instant in which
|
P
a
|
+
|
P
d
|
=
|
P
|
/
2
and
|
P
b
|
+
|
P
c
|
=
|
P
|
/
2
,orinwhich
|
P
a
|
+
|
P
d
|
=
|
P
|
/
2
+1and
|
P
b
|
+
|
P
c
|
=
|
P
|
/
2
−
1.This
completes the proof of the lemma.
We now show how to use Lemma 5 in order to prove Theorem 2.
Let
P
be any point set. Assume that no two points of
P
have the same
y
-coordinate.
Such a condition is easily met after rotating the Cartesian axes. Denote by
l
a vertical
straight line directed towards increasing
y
-coordinates. Each of
P
1
(
l
) and
P
2
(
l
) is con-
vex and one-sided with respect to
l
. By Lemma 1, there exist increasing-chord graphs
G
1
=(
P
1
(
l
)
,S
1
) and
G
2
=(
P
2
(
l
)
,S
2
) with
|
S
1
|
<
2
|
P
1
(
l
)
|
and
|
S
2
|
<
2
|
P
2
(
l
)
|
.
Then, graph
G
(
P,S
1
∪
edges and contains
an increasing-chord path between every pair of vertices in
P
1
(
l
) and between every pair
of vertices in
P
2
(
l
).However,
G
does not have increasing-chord paths between any pair
(
a, b
) of vertices such that
a
S
2
) has less than 2(
|
P
1
(
l
)
|
+
|
P
2
(
l
)
|
)=2
|
P
|
P
2
(
l
).
We now present and prove the following claim. Consider a convex point set
Q
and
a directed straight line
d
1
not orthogonal to any line through two points of
Q
. Then,
there exists a geometric graph
H
(
Q,R
) that contains an increasing-chord path between
every point in
Q
1
(
d
1
) and every point in
Q
2
(
d
1
),such that
∈
P
1
(
l
) and
b
∈
|
R
|∈
O
(
|
Q
|
log
|
Q
|
).
