Covering Partial Cubes with Zones - Discrete and Computational Geometry and Graphs - page 3

2.1 Hyperplane Arrangements

The dual graph of a simple 1 arrangement of n hyperplanes in

d is a partial cube
of dimension n . The partial cube covering problem becomes the following: given
a simple hyperplane arrangement, find a smallest subset S of the hyperplanes
such that every cell of the arrangement is bounded by at least one hyperplane
in S .

R

The case of line arrangements was
first considered in [ 3 ]. In fact it was
this problem that motivated us to
investigate the generalization to par-
tial cubes. The best known lower and
upper bounds for line arrangements
on

| S | are of order n/ 6and n −

O ( √ n log n )(see[ 1 ]). The complexity
status of the optimization problem is
unknown (Fig. 2 ).
Instead of lines and hyperplanes it is also possible to consider Euclidean or
spherical arrangements of pseudo-lines and pseudo-hyperplanes, their duals are
still partial cubes. Actually, all the cited results apply to the case of arrangements
of pseudo-lines.

Fig. 2. An arrangement of 4 lines superim-
posed with its dual.

Spherical arrangements of pseudo-
hyperplanes are equivalent to oriented
matroids, this is the Topological Rep-
resentation Theorem of Folkman and
Lawrence. The pseudo-hyperplanes
correspond to the elements of the ori-
ented matroid and the cells of the
arrangement correspond to the topes
of the oriented matroid. Hence our
covering problem asks for a minimum
size set C of elements such that for
every tope T there is an element c

∈ C

such that T c is another tope. For

more on oriented matroids we refer
to [ 2 ].

↕

Fig. 3. Flip graph of acyclic orientations
of the 4-cycle.

2.2 Acyclic Orientations

From a graph G =( V,E ), we can define a partial cube H in which every vertex
is an acyclic orientation of G , and two orientations are adjacent whenever they
differ by a single edge reversal ( flip ). This partial cube has dimension equal to
the number of edges of G . It is also the dual graph of the arrangement of the

| E |

hyperplanes of equation x i = x j for ij

∈ E in R

V . Every cell of this arrangement

1 An arrangement is called simple if any d + 1 hyperplanes have empty intersection.