Advertisement
Published in:
2006 | OriginalPaper | Chapter
Visibility Maps of Segments and Triangles in 3D
Authors : Esther Moet, Christian Knauer, Marc van Kreveld
Published in: Computational Science and Its Applications - ICCSA 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Let
T
be a set of
n
disjoint triangles in three-dimensional space, let
s
be a line segment, and let
t
be a triangle, both disjoint from
T
. We consider the visibility map of
s
with respect to
T
, i.e., the portions of
T
that are visible from
s
. The visibility map of
t
is defined analogously. We look at two different notions of visibility: strong (complete) visibility, and weak (partial) visibility. The trivial Ω(
n
2
) lower bound for the combinatorial complexity of the strong visibility map of both
s
and
t
is almost tight: we prove an
O
(
n
2
log
n
) upper bound for both structures. Furthermore, we prove that the weak visibility map of
s
has complexity Θ(
n
5
), and the weak visibility map of
t
has complexity Θ(
n
7
). If
T
is a polyhedral terrain, the complexity of the weak visibility map is Ω(
n
4
) and
O
(
n
5
), both for a segment and a triangle. We also present efficient algorithms to compute all discussed structures.