RCBR (version 0.6.2)

NICER: New Incremental Cell Enumeration (in) R

Description

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

Usage

NICER(A, b, initial = c(0, 0), verb = TRUE, epsbound = 1, epstol = 1e-07)

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

Arguments

A

is a n by 2 matrix of slope coefficients

b

is an n vector of intercept coefficients

initial

origin for the interior point vectors w

verb

controls verbosity of Mosek solution

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." When the hyperplanes are in general position the number of polytopes (cells) is determined by the elegant formula of Zazlavsky (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. Current version is intended for use with \(d = 2\), but the algorithm is adaptable to \(d > 2\), and there is an experimental version called NICERd in the package.

References

Alexanderson, G.L and J.E. Wetzel, (1981) Arrangements of planes in space, Discrete Math, 34, 219--240. Gu, J. and R. Koenker (2020) Nonparametric Maximum Likelihood Methods for Binary Response Models with Random Coefficients, J. Am. Stat Assoc 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.

Examples

{
if(packageVersion("Rmosek") > "8.0.0"){
    A = cbind(c(1,-1,1,-2,2,1,3), c(1,1,1,1,1,-1,-2))
    B = matrix(c(3,1,7,-2,7,-1,1), ncol = 1)
    plot(NULL,xlim = c(-10,10),ylim = c(-10,10))
    for (i in 1:nrow(A))
	  abline(a = B[i,1]/A[i,2], b = -A[i,1]/A[i,2],col = i)
    f = NICER(A, B)
    for (j in 1:ncol(f$SignVector))
    	  points(f$w[1,j], f$w[2,j], cex = 0.5)
    }
}