NICERd {RCBR}

New (Accelerated) Incremental Cell Enumeration (in) R

Description

Find interior points and cell counts of the polygons (polytopes) formed by a hyperplane arrangement.

Usage

NICERd(
  A,
  b,
  initial = rep(0, ncol(A)),
  verb = TRUE,
  accelerate = FALSE,
  epsbound = 1,
  epstol = 1e-07
)

Arguments

A

is a n by d matrix of hyperplane slope coefficients

b

is an n vector of hyperplane intercept coefficients

initial

origin for the interior point vectors w

verb

controls verbosity of Mosek solution

accelerate

allows the option to turn off acceleration step (turned off by default)

epsbound

is a scalar tolerance controlling how close the witness point can be to an edge of the polytope

epstol

is a scalar tolerance for the LP convergence

Details

Modified version of the algorithm of Rada and Cerny (2018). The main modifications include preprocessing as hyperplanes are added to determine which new cells are created, thereby reducing the number of calls to the witness function to solve LPs, and treatment of degenerate configurations as well as those in "general position." (for d=2 for now). When the hyperplanes are in general position the number of cells (polytopes) is determined by the elegant formula of Zaslavsky (1975)

m = {n \choose d} + n + 1

. In degenerate cases, i.e. when hyperplanes are not in general position, the number of cells is more complicated as considered by Alexanderson and Wetzel (1981). The function polycount is provided to check agreement with their results in an effort to aid in the selection of tolerances for the witness function for arrangement in d=2. The current version is intended mainly for use with d = 2, but the algorithm is adapted to the general position setting with d > 2, although it requires hyperplanes in general position and may require some patience when both the sample size is large. if hyperplanes not general position (i.e. all cross at origin), turn off accelerate

Value

A list with components:

• SignVector a n by m matrix of signs determining position of cell relative to each hyperplane.

• w a d by m matrix of interior points for the m cells

References

Alexanderson, G.L and J.E. Wetzel, (1981) Arrangements of planes in space, Discrete Math, 34, 219–240. Rada, M. and M. Cerny (2018) A new algorithm for the enumeration of cells of hyperplane arrangements and a comparison with Avis and Fukada's reverse search, SIAM J. of Discrete Math, 32, 455-473. Zaslavsky, T. (1975) Facing up to arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes, Memoirs of the AMS, Number 154.