Home | Bookmarks | Papers | Blog |

Esther Ezra, Sariel Har-Peled, Haim Kaplan, and Micha Sharir.

This work is motivated by several basic problems and techniques that rely on space decomposition of arrangements of hyperplanes in high-dimensional spaces, most notably Meiser's 1993 algorithm \cite{m-plah-93} for point location in such arrangements. A standard approach to these problems 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 with the subset of hyperplanes that cross the cell. 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 a suitably
defined corresponding range space. Another parameter, which we
refer to here as the *combinatorial dimension*, is the
maximum 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 (and later Clarkson and Shor's)
random sampling technique.

We re-examine these parameters for the two main space
decomposition techniques - *bottom-vertex triangulation*, and
*vertical decomposition*, including their explicit dependence on
the dimension $d$, 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.

Our main application is to point location in an arrangement of $n$ hyperplanes is $\Re^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 some increase in the preprocessing cost and storage (which seem to be stated incorrectly, and are not worked out, in Meiser's work). Our improved bounds rely on establishing several new structural properties and improved complexity bounds for vertical decomposition, which are of independent interest, and which we expect to find additional applications.

PDF. : arXiv : DCG : DBLP.

Last modified: Mon 2022-07-25 13:42:39 UTC 2022 by Sariel Har-Peled