Combinatorial and algorithmic analysis of stabbing and visibility problems in three-dimensional space

Candidate: Pellegrini,Marco


Given a set $T$ of triangles in 3-space, with $\vert T\vert$ = $n$, let ${\cal S}$($T$) be the set of all lines stabbing the set $T$. The combinatorial descriptive complexity of ${\cal S}$($T$) is denoted by #${\cal S}$($T$). The following questions about ${\cal S}$($T$) are considered in this thesis: (a) answer the query given a line $l$, is $l$ $\in$ ${\cal S}$($T$)? (query problem). (b) decide whether ${\cal S}$($T$) $\ne$ 0 (existence problem). (c) Give upper and lower bounds on #${\cal S}$($T$). The following results are shown in this thesis: (1) There is an $\Omega (n\sb3$) lower bound for #${\cal S}$($T$). Also ${\cal S}$($T$) may have $\Omega (n\sb2$) connected components. (2) There is an $O (n\sp{3+\epsilon}$) upper bound on #${\cal S}$($T$). Within the same time bound it is possible to solve the existence problem. (3) The existence problem for triangles on a set of planes with $g$ different plane inclinations can be solved in $O(g\sp2 n\sp2 {\rm log}\ n$) time. (4) The query problem is solvable in $O(n\sp{2+\epsilon}$) preprocessing and storage and logarithmic $O({\rm log}\ n$) query time. (5) The results (1), (2), (3) and (4) extend, with the same asymptotic bounds, to sets of convex polyhedra with total complexity $n$. Given a set $T$ of n disjoint triangles, the ray shooting problem for $T$ is the following: preprocess $T$ so to be able to answer queries of the form Given a ray $\rho$, does $\rho$ hit any triangle in $T$?. The following results are shown in this thesis: (1) Using $O(n\sp{3+\epsilon}$) randomized preprocessing time and storage we can solve ray-shooting queries in $O (\sqrt{n}{\rm log}\sp2 n$) worst case query time. (2) If we are given $m$ $>$ $n\sp{7/5}$ rays and $n$ disjoint triangles, we can answer all the ray shooting queries in $O (m\sp{5/6-\delta} n\sp{5/6+5\delta}$log $n$ + $m$ log $n$ + $n$ log $m$) randomized expected time and $O (m+n$) space, for every $\delta$ $>$ 0. The multiplicative constants depend on $\delta$. (3) Given $m$ rays and $n$ axis-oriented boxes we can answer ray shooting queries in randomized expected time $O(m\sp{3/4-\delta}n\sp{3/4+3\delta}\log\sp3n+m$ log$\sp3n+n$ log $m$) and $O(m+n$) space, for 1/28 $<$ $\delta$ $<$ 1/9. The multiplicative constants depend on $\delta$.