Information Technology Reference
In-Depth Information
L
2
, the arrangement
L
1
lies in the closure of a single face
F
2
of the arrangement
arc in
L
2
, and vice versa
L
1
.We
construct a plane graph
H
representing the tangencies between the edges of the two
arrangements: place a vertex on the relative interior of each edgeof
L
2
lies in the closure of a single face
F
1
of the arrangement
L
1
incident to
F
1
and each edgeof
L
2
incident to
F
2
. Join two vertices,
v
and
u
,byanedgeifftheir
corresponding edges of the arrangements,
e
u
and
e
v
,aretangent to each other. To see
that
H
is indeed planar, note that each edge
uv
can be drawn closely following the arcs
e
u
and
e
v
to their intersection point in such a way that
H
has no crossings. As every arc
in
L
2
,thegraph
H
has exactly 200
2
edges. By Theorem 8,
H
has at most 2
ʻ
3
(400) vertices. However,
L
1
is tangent to all arcs in
200
2
2
ʻ
3
(400)
>
200
2
|
E
(
H
)
|
|
≥
400
>
3
.
3
,
|
V
(
H
)
4
·
400 ln400 + 6
·
which contradicts Euler'sformula.
L
2
are not necessarily connected but they have the property that every pseudo-segment in
L
1
lies in the same face of
Note that Lemma 4 easily generalizes to the case when the arrangements
L
1
and
L
2
, and vice versa.
It is now easy to see that Lemma 3 follows directly from Lemma 4: if 200 edges of the
simple topological graph
G
are disjoint from another set of 200 edges of
G
,thenaset
of the corresponding 200 edges of the tangled-thrackle
G
are tangent to corresponding
other set of 200 edges of
G
.
Proof of Theorem 2:
The statement follows by combining Theorem 1 and Lemma 3.
We now show an analogue of Lemma 4 where we drop the condition that the ar-
rangements
L
1
and
L
2
are connected. We find this interesting for its own sake.
L
1
∪L
2
be an arrangements of pseudo-segments such thatevery
Proposition 1.
Let
L
1
is tangenttoall arcs in
L
2
.Then
L
1
or
L
2
contains at most 400 arcs.
arc in
L
1
and
L
2
contain at least 400 arcs. Without
Proof:
Suppose to the contrary, that both
loss of generality, we may assume
|L
1
|
=
|L
2
|
= 400. The difference from Lemma 3
is that the arrangement
L
1
or
L
2
may not be connected, and so the arcs in
L
1
could be
distributed in several faces of the arrangement
L
2
.
Consider an arc
∈L
1
, and denote by
s
the number of other arcs in
L
1
that intersect
,where0
≤
s
≤
399.Then
contains precisely
s
+1edges of the arrangement
L
1
.
Partition
into two Jordan arcs:
a
ↂ
consists of the first
(
s
+1)
/
2
edges along
,
and
b
=
L
2
. By the pigeonhole principle,
we may assume w.l.o.g.that
a
is tangent to at least 200 arcs in
\
a
. Recall that
is tangent to all 400 arcs in
L
2
ↂL
2
be
L
2
.Let
a set of 200 arcs in
L
2
that are tangent to
1
. By construction,
a
intersects at most
L
1
ↂL
1
of 200 arcs in
s/
2
≤
200 arcs in
L
1
. Consequently, there is a set
L
1
that do
L
1
. Since every
not
intersect
a
. Observe that
a
lies in a single face of the arrangement
L
2
intersects
a
, all arcs in
L
2
lie in the same face of the arrangement
L
1
.
arc in
L
1
ↂL
1
and
L
2
ↂL
2
of size
|L
1
|
|L
2
|
We h ave f ound subsets
=
= 200 such that
L
1
is tangent to all arcs in
L
2
;andallarcsof
L
1
lie in the same face of
L
2
every arc in
and vice versa. This contradicts Lemma 4 and the remark following its proof.
