Information Technology Reference
In-Depth Information
The application of the claim with
Q
=
P
and
d
1
=
l
provides a graph
H
(
P,R
)
that contains an increasing-chord path between every pair (
a, b
) of vertices such that
a
∈
P
1
(
l
) and
b
∈
P
2
(
l
).Thus, the union of
G
and
H
is an increasing-chord graph
with
O
(
) edges spanning
P
. Therefore, the above claim implies Theorem 2.
We s h ow a n i n ductive algorithm to construct
H
.Let
f
(
Q,
d
1
) be the number of
edges that
H
hasasaresult of the application of ouralgorithm on a point set
Q
and
a directed straight-line
d
1
. Also, let
f
(
n
)=max
|
P
|
log
|
P
|
{
f
(
Q,
d
1
)
}
, where the maximumis
among all point sets
Q
with
n
=
points and among all the directed straight-lines
d
1
that are not orthogonal to any line through two points of
Q
.
Let
Q
be any convex point set with
n
points and let
d
1
be any directed straight
line not orthogonal to any line through two points of
Q
. By Lemma 5, there exists a
directed straight line not orthogonal to any line through two points of
Q
and such that
the (
d
1
,
d
2
)-partition of
Q
is balanced.
Let
Q
a
=
Q
1
(
d
1
)
|
Q
|
∩
Q
1
(
d
2
),let
Q
b
=
Q
1
(
d
1
)
∩
Q
2
(
d
2
),let
Q
c
=
Q
2
(
d
1
)
∩
Q
1
(
d
2
),
and let
Q
d
=
Q
2
(
d
1
)
∩
Q
2
(
d
2
).
Q
c
is convex and one-sided with respect to
d
2
.ByLemma1there
exists an increasing-chord graph
H
1
(
Q
a
∪
Point set
Q
a
∪
Q
c
,R
1
) with
|
R
1
|
<
2(
|
Q
a
|
+
|
Q
c
|
) edges.
Analogously, by Lemma 1 there exists an increasing-chord graph
H
2
(
Q
b
∪
Q
d
,R
2
)
with
) edges.
Hence, there exists a graph
H
3
(
Q,R
1
∪
|
R
2
|
<
2(
|
Q
b
|
+
|
Q
d
|
R
2
) with
|
R
1
∪
R
2
|
<
2(
|
Q
a
|
+
|
Q
c
|
+
|
=2
n
edges containing an increasing-chord path between every
point in
Q
a
and every point in
Q
c
, and between every point in
Q
b
and every point in
Q
d
.However,
G
does not have an increasing-chord path between any point in
Q
a
and
any point in
Q
d
, and does not have an increasing-chord path between any point in
Q
b
and any point in
Q
c
.
By Lemma 5, it holds that
Q
b
|
+
|
Q
d
|
)=2
|
Q
|
n
2
+1 and
n
2
+1. By definition,
|
Q
a
|
|
Q
d
|≤
|
Q
b
|
|
Q
d
|≤
+
+
f
(
2
+1).Analogously, it holds that
f
(
Q
b
∪ Q
c
,
d
1
)
≤ f
(
|Q
b
|
+
|Q
c
|
)
≤ f
(
2
+1). Hence,
f
(
n
)
≤
2
n
+2
f
(
2
+1)
∈
O
(
n
log
n
). This proves the claim and hence Theorem 2.
we have
f
(
Q
a
∪
Q
d
,
d
1
)
≤
f
(
|
Q
a
|
|
Q
d
|
≤
+
)
5
Conclusions
We considered the problem of constructing increasing-chord graphs spanning point sets.
We proved that, for every point set
P
, there exists a planar increasing-chord graph
G
(
P
,S
) with
P
ↆ
P
and
|
P
|∈
O
(
|
P
|
). We also proved that, for every convex point
set
P
, there exists an increasing-chord graph
G
(
P,S
) with
|
S
|∈
O
(
|
P
|
|
P
|
log
).
Despite our research efforts, the main question on this topic remains open:
Problem 1.
Is it true that, for every (convex) point set
P
, there exists an increasing-
chord planar graph
G
(
P,S
)?
One of the directions we took in order to tackle this problem is to assume that the
points in
P
lie on a constant number of straight lines. While a simple modification of the
proof of Lemma 1 allows us to prove that an increasing-chord planar graph always exists
spanning a set of points lying on two straight lines, it is surprising and disheartening
that we could not prove a similar result for sets of points lying on three straight lines.
