Information Technology Reference
In-Depth Information
x
l
(
u
)
x
r
(
u
)
y
t
(
u
)
y
t
(
P
)
y
b
(
P
)
R
(
u
)
P
(
u, v
)
R
(
v
)
R
(
z
)
y
b
(
u
)
Fig. 2.
Geometric description of a region
R
(
u
) and of a pipe
P
(
u, v
), after procedure P
IPE
E-
QUALIZER
has been applied
can be categorized as either horizontal or vertical, we can label its pipe
P
(
u,v
) as ei-
ther
horizontal
or
vertical
accordingly. Also, we can determine the minimum
and maximum
y
-coordinate (
x
-coordinate) that a horizontal (vertical) edge (
u,v
) can
assume while placing both its endvertices inside their regions. In the following we de-
scribe pipe
P
(
u,v
) by means of these coordinates, which are denoted by
y
b
(
P
) and
y
t
(
P
) (
x
l
(
P
) and
x
r
(
P
)), respectively. See
horizontal
pipe
P
(
u,v
) in Fig.2.
Also note that, if a vertex
v
of degree 2 is incident to two horizontal (vertical) edges
(
u,v
) and (
v,z
), then replacing
v
and its incident edges with a horizontal (vertical)
edge (
u,z
) yields an equivalent instance. Hence, we assume that, if there exists a vertex
of degree 2, then it is incident to both a horizontal and a vertical edge.
As a preliminary step of the algorithm, we initialize the geometric description of each
pipe
P
(
u,v
) as follows. If
P
is
vertical
,thenset
x
r
(
P
)=
min
(
x
r
(
u
)
,x
r
(
v
)) and
x
l
(
P
)=
max
(
x
l
(
u
)
,x
l
(
v
)).If
P
is
horizontal
,thenset
y
t
(
P
)=
min
(
y
t
(
u
)
,y
t
(
v
))
and
y
b
(
P
)=
max
(
y
b
(
u
)
,y
b
(
v
)). Here and in the following, whenever a vertex region
R
(
w
) (a pipe
P
(
u,v
)) is modified by the algorithm, we assume the pipes incident to
w
(the regions
R
(
u
) and
R
(
v
)) to be modified accordingly.
In order to ensure that
horizontal
(
vertical
) pipes whose edges belong to the
same horizontal (vertical) path have the same geometric description, we refine the pipes
by applying the following procedure, that we call P
IPE
E
QUALIZER
.Aslong as there ex-
ist two
vertical
pipes
P
(
u,v
) and
P
(
v,w
) incident to the same vertex
v
such that
x
l
(
P
)
=
x
r
(
P
),set
x
l
(
P
)=
x
l
(
P
)=
max
(
x
l
(
P
)
,x
l
(
P
))
and
x
r
(
P
)=
x
r
(
P
)=
min
(
x
r
(
P
)
,x
r
(
P
)).Analogously, as long as there exist
two
horizontal
pipes
P
(
u,v
) and
P
(
v,w
) incident to the same vertex
v
such that
y
b
(
P
)
=
x
l
(
P
) or
x
r
(
P
)
=
y
t
(
P
),set
y
b
(
P
)=
y
b
(
P
)=
max
(
y
b
(
P
)
,y
b
(
P
))
and
y
t
(
P
)=
y
t
(
P
)=
min
(
y
t
(
P
)
,y
t
(
P
)). See pipe
P
(
u,v
) in Fig.2afterthe
application of P
IPE
E
QUALIZER
.
We then perform the following procedure, that we call P
IPE
C
HECKER
.Itfirstchecks
whether there exists a pipe
P
such that
x
r
(
P
)
<x
l
(
P
) or
y
t
(
P
)
<y
b
(
P
). Then, it
checks whether there exists a PP-overlap between two pipes
P
(
u,v
) and
P
(
w,z
) such
that: (
i
) neither of
R
(
u
) or
R
(
v
) has a VP-overlap with
P
(
w,z
);and(
ii
) neither of
R
(
w
) or
R
(
z
) has a VP-overlap with
P
(
u,v
). If one of the two checks succeeds, then
we conclude that instance
I
is negative, otherwise we proceed with the algorithm.
In the following, every time a pipe is modified, we will apply procedure P
IPE
E-
QUALIZER
to extend this modification to other pipes, and procedure P
IPE
C
HECKER
to
test whether such modifications resulted in uncovering anegative instance.
=
y
b
(
P
) or
y
t
(
P
)
