## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

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

Duration: 30 minutes

Location: CAB G51

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.

Information for students and suggested topics for student talks