Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

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

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Micha Sharir (Tel Aviv University)

Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, point location, and a very long title

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