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

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

**Date and Time**: Thursday, October 20, 2016, 12:15 pm

**Duration**: 30 minutes

**Location**: OAT S15/S16/S17

**Speaker**: Micha Sharir (Tel Aviv University)

This work is motivated by several basic problems that rely on space decomposition of arrangements of hyperplanes in high-dimensional spaces, most notably Meiser's 1993 algorithm for point location in such arrangements. A standard approach to these problem is via random sampling, in which one draws a random sample of the hyperplanes, constructs a suitable decomposition of its arrangement, and recurses within each cell of the decomposition. The efficiency of the resulting algorithm depends on the quality of the sample, which is controlled by various parameters. One of these parameters is the classical VC-dimension, and its associated primal shatter dimension, of the corresponding range space. Another parameter, which we refer to here as the combinatorial dimension, is the number of hyperplanes that are needed to define a cell that can arise in the decomposition of some sample of the input hyperplanes; this parameter arises in Clarkson's random sampling technique. We re-examine these parameters for the two main space decomposition techniques---bottom-vertex triangulation, and vertical decomposition, and discover several unexpected phenomena, which show that, in both techniques, there are large gaps between the VC-dimension (and primal shatter dimension), and the combinatorial dimension. For vertical decomposition, the combinatorial dimension is only $2d$ but the primal shatter dimension is at least $\Omega(d^2)$ and the VC-dimension is at most $O(d^3)$. For bottom vertex triangulation, both the primal shatter dimension and the combinatorial dimension are $\Theta(d^2)$, but there is still a significant gap between them, as the combinatorial dimension is $d(d+3)/2$, whereas the VC-dimension is at least $d(d+1)$; we do not know whether the VC-dimension is $O(d^2)$. Our main application is to point location in an arrangement of $n$ hyperplanes is $R^d$, in which we show that the query cost in Meiser's algorithm can be improved if one uses vertical decomposition instead of bottom-vertex triangulation, at the cost of increasing the preprocessing cost and storage. Concretely, a query takes $O(d^3\log n)$ time, instead of $O(d^4\log d\log n)$, We also correct some problems in the analysis of storage and preprocessing cost, and obtain a larger bound on these parameters, which also applies, more or less, for our technique. Joint work with Esther Ezra, Sariel Har-Peled, and Haim Kaplan.

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

Previous talks by year: 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