Tag - Linear Algebra

\(d\) hyperplanes intersection bounds Sun, Jan 17, 2016 00:00 CET

We bound the position of the \(0\)-cells of an arrangement of hyperplanes in \(\mathbb{R}^d\). This allows, for example, to build an hypercube that intersects all cells of the arrangement. Such an hypercube must contain at least one point of each cell of the arrangement. When \(q > 0\), in order to fix which point of a \(q\)-cell we want to include in the hypercube, it suffices to add the \(n\) hyperplanes of equation \(x_i = 0\) to the arrangement. With those additional hyperplanes, the arrangement is such that each \(q\)-cell of the arrangement with \(q > 0\) contains a \(0\)-cell of the arrangement, hence, we only need the hypercube to intersect, for each \(0\)-cell \(\nu\) of the arrangement, an hypersphere of center \(\nu\) and arbitrarily small radius. The inequalities of the polyhedral set defining our hypercube will thus only depend on the position of the \(0\)-cells of our arrangement.

Gaussian elimination Fri, Jun 19, 2015 02:00 CEST

Python implementation.