Information Technology Reference
In-Depth Information
iff there exist
k
∈
[
d
] such that
|
x
k
−
y
k
|
|
x
i
−
y
i
|
<
1 for all
i
∈
[
d
]
\{
k
}
=1and
.It
remains to show that two cubes
ˆ
(
v
x
) and
ˆ
(
v
y
) have proper contact iff (
v
x
,v
y
)
∈
E
S
n
:
Suppose (
v
x
,v
y
)
∈
E
S
. Then, it holds
x
−
y
1
=1;thatis
∃
!
k
∈
[
d
] with
|
x
k
−
y
k
|
=1
|
x
i
−
y
i
|
=0for all
i
∈
[
d
]
\{
k
}
.Wlog let
x
≥
dom
y
. Consider the characteristic
and
y
of the cubes
ˆ
(
v
x
) and
ˆ
(
v
y
).Let
e
k
denote the
k
th
standard basis
corners
A
·
x
and
A
·
d
, then for the characteristic corners hold: (
A
vector of
e
k
.
This implies that the two cubes
ˆ
(
v
x
) and
ˆ
(
v
y
) have proper contact which is of size
cs
(
ˆ
(
v
x
)
, ˆ
(
v
y
)) = 1
R
·
x
−
A
·
y
)=
A
·
(
x
−
y
)=
A
·
−
ʵ
.
Suppose (
v
x
,v
y
)
/
∈
E
S
,then
x
−
y
1
≥
2. Either there is a coordinate
k
∈
[
d
],
such that
|
x
k
−
y
k
|≥
2 or there exist at least two coordinates
k,j
∈
[
d
] such that
|
x
k
−
y
k
|≥
1. It is easy to check, that in either case, there is a coordinate in (
A
·
x
−
A
·
y
)
1+
ʵ
, and hence, the cubes
ˆ
(
v
x
) and
ˆ
(
v
y
) are
which has an absolute valueof
≥
E
S
the space is sp(
ˆ
(
v
x
)
, ˆ
(
v
y
)
,e
k
)
disjoint. Thusfor(
v
x
,v
y
)
/
ʵ
for
k
=1
,...,d
.
We proceed with the translation vectors and moving sets: For
e
=(
v
x
,v
y
)
∈
≥
∈
E
S
,
there exists a unique
k
∈
[
d
] with
|
x
k
−
y
k
|
=1and
x
i
=
y
i
for
i
=
k
.Wlog we
assume
x
≤
dom
y
. Then, the direction vector is defined as
d
(
e
):=
e
k
and the moving
set as
M
(
e
):=
[
n
]
d
,z
k
>x
k
,z
i
=
x
i
for all
i
.
Observe that the translation vector
d
(
e
) of edge
e
is parallel to each of the following
crucial (
d
{
v
z
|
z
∈
=
k
}
1)-dimensional facets: These are facets realizing the contacts corresponding
to edges of type (
u,v
)
−
∈
E
\{
e
}
with
u
∈
M
(
e
) and
v/
∈
M
(
e
). Additionally, it holds
sp
ˆ
(
u
)
, ˆ
(
v
)
,d
i
for
w
that
r
i
(
w
)
ʴ
.
Following the same lines as the proof of Theorem 2, this shows that the construction
yields a UPCR with
d
-cubes for each subgraph of
≤
nʴ < ʵ
≤
∈{
u,v
}
∈
/
E
S
and
i
∈{
1
,...,d
}
n
.
S
5.2
Triangular Grid
Alam et al. [2] asked whether subgraphs of the triangular grid have UCuPCRs. In this
section, we answer this question affirmatively.
We introduce an unconventional definition of the triangular grid
T
m,n
=(
V
T
,E
T
)
of size
m
×
n
.For
i
∈
[
m
],and
j
∈
[
n
],thevertexsetis
V
:=
{
b
i,j
}∪{
t
i,j
}
.Thesetof
edges is
E
:=
i
=1
E
i
,where
E
1
:= (
x
i,j
,x
i,j
+1
) with
x
,
E
2
:= (
b
i,j
,t
i,j
),
E
3
:= (
b
i,j
,t
i,j−
1
),
E
4
:= (
b
i,j
,t
i−
1
,j−
1
),and
E
5
:= (
b
i,j
,t
i−
1
,j
), see also Figure 5.
For fixed
j
, we call the vertex set of type
∈{
b,t
}
x
i,j
}
i∈
[
m
]
a
line
and two neighboring lines a
level
.Edges between two lines are called
level edges
. Note that we have 2
n
lines.
{
t
2
,
0
b
2
,
0
t
1
,
0
b
1
,
0
t
0
,
0
...
b
0
,
0
b
1
,
0
b
4
,
0
(a) (b) (c)
Fig. 5. (a)
Triangular grid
T
4
,
2
; for thick edges, the moving sets are indicated by framed vertices
(b)
UCuPCR
ˆ
of
T
4
,
2
(c)
Illustration of modification step.
