BigObject HyperplaneArrangement<Scalar>

from application fan

A hyperplane arrangement. The hyperplane arrangement is given by a matrix HYPERPLANES whose rows are the linear equations of the hyperplanes and an optional support cone. The support cone defaults to being the whole space. Duplicate hyperplanes are ignored, as well as hyperplanes that intersect the support cone trivially. The support cone is subdivided by the hyperplanes resulting in a fan CELL_DECOMPOSITION.

Type Parameters:

Scalar: numeric data type used for the coordinates, must be an ordered field. Default is Rational.

Example:

Take the 2-dimensional positive orthant and slice it along the ray through (1,1)

 > $HA = new HyperplaneArrangement(INPUT_HYPERPLANES=>[[-1,1]], "SUPPORT.INPUT_RAYS"=>[[1,0],[0,1]]);
 > $CD = $HA->CELL_DECOMPOSITION;
 > print $CD->RAYS;
 0 1
 1 0
 1 1

 > print $CD->MAXIMAL_CONES;
 {0 2}
 {1 2}

Permutations:

ConesPerm:

permuting the RAYS

These properties are for input only. They allow redundant information.

INPUT_HYPERPLANES

A matrix containing the input hyperplanes of the arrangement as rows.

Type:

Matrix<Scalar,NonSymmetric>

SUPPORT

A cone being subdivided by the HYPERPLANES defaults to the whole space.

Type:

Cone<Scalar>

Example:

Take the 2-dimensional positive orthant and slice it along the ray through (1,1)

 > $HA = new HyperplaneArrangement(INPUT_HYPERPLANES=>[[-1,1]], "SUPPORT.INPUT_RAYS"=>[[1,0],[0,1]]);
 > $CD = $HA->CELL_DECOMPOSITION;
 > print $CD->RAYS;
 0 1
 1 0
 1 1

 > print $CD->MAXIMAL_CONES;
 {0 2}
 {1 2}

Example:

Subdivide the two-dimensional space along the axes

 > $HA = new HyperplaneArrangement(INPUT_HYPERPLANES=>[[1,0],[0,1]]);
 > $CD = $HA->CELL_DECOMPOSITION;
 > print $CD->RAYS;
 -1 0
 0 -1
 0 1
 1 0

 > print $CD->MAXIMAL_CONES;
 {0 1}
 {0 2}
 {1 3}
 {2 3}

 > print $CD->COMPLETE;
 true

These properties capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.

CELL_SIGNATURES

The i-th entry is the signature of the i-th maximal cone of the CELL_DECOMPOSITION.

Type:

Array<Set<Int>>

Example:

Take the 2-dimensional positive orthant and slice it along the ray through (1,1)

 > $HA = new HyperplaneArrangement(INPUT_HYPERPLANES=>[[-1,1]], "SUPPORT.INPUT_RAYS"=>[[1,0],[0,1]]);
 > $CD = $HA->CELL_DECOMPOSITION;
 > print $CD->MAXIMAL_CONES;
 {0 2}
 {1 2}

 > print $HA->CELL_SIGNATURES;
 {}
 {0}

 > print $HA->cell_to_signature($CD->MAXIMAL_CONES->[0]);
 {}

 > print $HA->cell_to_signature($CD->MAXIMAL_CONES->[1]);
 {0}

 > print $HA->signature_to_cell($HA->CELL_SIGNATURES->[0]);
 0

 > print $CD->MAXIMAL_CONES->[$HA->signature_to_cell($HA->CELL_SIGNATURES->[0])];
 {0 2}

These properties capture geometric information of the object. Geometric properties depend on geometric information of the object, like, e.g., vertices or facets.

CELL_DECOMPOSITION

Slicing the SUPPORT along every hyperplane of HYPERPLANES one gets a polyhedral fan.

Type:

PolyhedralFan<Scalar>

Example:

Take the 2-dimensional positive orthant and slice it along the ray through (1,1)

 > $HA = new HyperplaneArrangement(INPUT_HYPERPLANES=>[[-1,1]], "SUPPORT.INPUT_RAYS"=>[[1,0],[0,1]]);
 > $CD = $HA->CELL_DECOMPOSITION;
 > print $CD->RAYS;
 0 1
 1 0
 1 1

 > print $CD->MAXIMAL_CONES;
 {0 2}
 {1 2}

HYPERPLANES

A matrix containing the hyperplanes of the arrangement as rows. This matrix is obtained from INPUT_HYPERPLANES by removing duplicates and also removing hyperplanes that are obsolete wrt the SUPPORT cone.

Type:

Matrix<Scalar,NonSymmetric>

Example:

The same hyperplane with opposing directions.

 > $HA = new HyperplaneArrangement(INPUT_HYPERPLANES=>[[1,-1],[-1,1],[1,1]]);
 > print $HA->HYPERPLANES;
 1 -1
 1 1

Example:

A hyperplane that does not cut through the SUPPORT

 > $HA = new HyperplaneArrangement(INPUT_HYPERPLANES=>[[1,1]], "SUPPORT.INEQUALITIES"=>unit_matrix(2));
 > print $HA->HYPERPLANES;
 

These methods capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.

cell_to_signature

Given a maximal cone of CELL_DECOMPOSITION as Set<Int> containing the indices of the rays spanning it, return the signature of the cone as Set<Int> of indices of the HYPERPLANES that evaluate negatively on this cone.

Example:

Take the 2-dimensional positive orthant and slice it along the ray through (1,1)

 > $HA = new HyperplaneArrangement(INPUT_HYPERPLANES=>[[-1,1]], "SUPPORT.INPUT_RAYS"=>[[1,0],[0,1]]);
 > $CD = $HA->CELL_DECOMPOSITION;
 > print $CD->MAXIMAL_CONES;
 {0 2}
 {1 2}

 > print $HA->CELL_SIGNATURES;
 {}
 {0}

 > print $HA->cell_to_signature($CD->MAXIMAL_CONES->[0]);
 {}

 > print $HA->cell_to_signature($CD->MAXIMAL_CONES->[1]);
 {0}

 > print $HA->signature_to_cell($HA->CELL_SIGNATURES->[0]);
 0

 > print $CD->MAXIMAL_CONES->[$HA->signature_to_cell($HA->CELL_SIGNATURES->[0])];
 {0 2}

signature_to_cell

Given a signature as a Set<Int> of indices that indicate which HYPERPLANES should evaluate negatively (the remaining evaluate positively), return the maximal cone of CELL_DECOMPOSITION associated to this signature. The result the index of the maximal cone in the maximal cones of CELL_DECOMPOSITION.

Example:

Take the 2-dimensional positive orthant and slice it along the ray through (1,1)

 > $HA = new HyperplaneArrangement(INPUT_HYPERPLANES=>[[-1,1]], "SUPPORT.INPUT_RAYS"=>[[1,0],[0,1]]);
 > $CD = $HA->CELL_DECOMPOSITION;
 > print $CD->MAXIMAL_CONES;
 {0 2}
 {1 2}

 > print $HA->CELL_SIGNATURES;
 {}
 {0}

 > print $HA->cell_to_signature($CD->MAXIMAL_CONES->[0]);
 {}

 > print $HA->cell_to_signature($CD->MAXIMAL_CONES->[1]);
 {0}

 > print $HA->signature_to_cell($HA->CELL_SIGNATURES->[0]);
 0

 > print $CD->MAXIMAL_CONES->[$HA->signature_to_cell($HA->CELL_SIGNATURES->[0])];
 {0 2}