Department of Computer Science | Institute of Theoretical Computer Science | CADMO

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.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login