Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, December 18, 2007, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Micha Sharir (Tel Aviv Univ.)
Let P be a collection of k (possibly intersecting) convex polyhedra in \reals^3, and let \ell_0 be a fixed line, disjoint from all the polyhedra in P. We consider two related problems:
(1) Preprocess P into a data structure that supports fast (polylogarithmic) ray shooting queries for rays emanating from \ell_0 (or contained in lines passing through \ell_0).
(2) Bound the combinatorial complexity of the set of all lines that emanate from \ell_0 and are transversals to P.
In both cases, the challenge is to obtain bounds that depend *linearly* on n.
For ray-shooting, we get a bound on the storage (and preprocessing) required by the structure, which is close to nk^2 when the polyhedra are pairwise disjoint (and is then worst-case tight in some sense), and close to nk^5 when they may intersect.
For complexity of the transversal space, we get a bound close to nk, which is almost worst-case tight.
Several related problems are also discussed.
Joint work (Ray shooting in ESA'07; transversals in preparation) with Haim Kaplan and Natan Rubin.
Automatic MiSe System Software Version 1.4803M | admin login