A Characterization of Link-2 LR-visibility Polygons with Applications - Discrete and Computational Geometry and Graphs - page 162

B(v )

F(v )

1

2

q

q

B(q)

v

F(q)

v 2

v 1

F(v )
3

F(p) B(p)

p

p

(c)

(a) (b)

Fig. 1. Forward, backward ray-shootings and components.

Let u , v denote two boundary points of P , and let P [ u, v ]and P ( u, v ) denote
the closed and open clockwise chains of P from u to v , respectively. We define
P [ r, B ( r )] and P [ F ( r ) ,r ]asthe backward component and forward component of
the reflex vertex r , respectively. The point r is referred to as the defining vertex
of its backward or forward component. See Fig. 1 . A component is said to be
non-redundant if it does not contain any other component, no matter which is
the forward or backward component. Note that some points of a component of
r may not visible from r . The following simple observation can also be made.

Observation 1. No point outside of the backward (forward) component of a reflex
vertex r is visibile from Succ ( r ) ( Pred ( r ) ). Moreover, P ( B ( r ) ,r ) ( P ( r, F ( r )) is
the first boundary chain, immediately after r anti-clockwise (clockwise), which is
invisible from Succ ( r ) ( Pred ( r ) ).

The known characterization of LR -visibility polygons is given in terms of the
non-redundant components.

Theorem 1 (See [ 14 ]) . A polygon P is not LR -visible if and only if it has k
non-redundant components such that each of them exactly intersects with k other
components, where 0 k ≤ ≤ k − 3 .

3 Characterizing Link-2 LR -visibility Polygons

In this section, we assume that the given polygon P is not LR -visible. We will
give a characterization of link-2 LR -visibility polygons by generalizing the known
result on the LR -visibility polygons (Theorem 1 ). By introducing the new con-
cepts of link-2 ray-shootings and components, we can generalize the forbidden
patterns for LR -visibility polygons into those for link-2 LR -visibility polygons.
Suppose that all non-redundant components in the polygon P have been
computed. Given a boundary point p , all boundary points can be ordered in
a clockwise scan of P , starting at p .If x is encountered before y , we simply
write x< p y . Assume that r is a vertex whose backward component P [ r, B ( r )]
is non-redundant. Let BB 1( r )( BF 1( r )) denote the largest ( smallest ) reflex ver-
tex, with respect to r , which is link-2 visible from Succ ( r ) but Pred ( BB 1( r )))