key: cord-0047235-5ngorenl
authors: Kastner, Lars; Panizzut, Marta
title: Hyperplane Arrangements in polymake
date: 2020-06-06
journal: Mathematical Software - ICMS 2020
DOI: 10.1007/978-3-030-52200-1_23
sha: 28d6057421b59ba19ee8056b15f23267fbe1ad02
doc_id: 47235
cord_uid: 5ngorenl

Hyperplane arrangements form the latest addition to the zoo of combinatorial objects dealt with by polymake. We report on their implementation and on a algorithm to compute the associated cell decomposition. The implemented algorithm performs significantly better than brute force alternatives, as it requires fewer convex hulls computations. The implementation is included in polymake since release 4.0.

Hyperplane arrangements are ubiquitous objects appearing in different areas of mathematics such as discrete geometry, algebraic combinatorics and algebraic geometry. A common theme is to understand the combinatorics and the topology of the cells in the complement of the arrangement. Combinatorics and its connections to other areas of mathematics are the focus of the software framework polymake [GJ00] , hence hyperplane arrangements form an almost mandatory addition to the objects available. We will discuss the implementation, such as the datatypes and properties, as well as some basic algorithms for analyzing hyperplane arrangements.

One of the main advantages of polymake are its various interfaces to other software. This allows keeping the codebase slim, while using powerful software developed by experts from other fields. Still polymake provides basic algorithms for many tasks, in case other software is not available. Hence the idea of the hyperplane arrangements is to provide a datatype with basic functionality as a basis for future interfaces to other software, e.g. to ZRAM [Brü+99] for computing the cell decomposition from the hyperplanes. Nevertheless, the polymake implementation of hyperplane arrangements comes with a basic algorithm for computing the associated cell decomposition that performs significantly better than brute force alternatives. Thus, we will discuss the main ideas of this algorithm in this article as well.

The combinatorics of hyperplane arrangements in real space is linked to zonotopes. Each arrangement endows the support space with a fan structure which is the normal fan of a zonotope. Each hyperplane subdivides the space in two halfspaces. Therefore we can encode relative positions of points with respect to the arrangement. In other words, hyperplane arrangements are examples of (oriented) matroids. Moreover, the hyperplanes in an arrangement can be seen as mirrors hyperplanes of a reflection group.

An interesting application is in Geometric Invariant Theory. GIT constructs quotients of algebraic varieties modulo group actions. The quotients depend on the choice of a linearized ample line bundle. Variation of geometric invariant theory quotients studies how quotients vary when changing the line bundle. Under some hypothesis the classes of equivalent quotients are convex subsets, called chambers. The walls among chambers are defined by certain hyperplane arrangements, see [DH98, Example 3.3.24].

We begin with the basic definitions in the theory of hyperplane arrangements following our implementation in polymake. 

Every hyperplane in the arrangement subdivides the space into two halfspaces

We remark that in the definition we allow duplicate hyperplanes, but from each hyperplane arrangement we can construct a reduced one. Let H be a hyperplane arrangement given by the hyperplanes {h 1 , h 2 , . . . , h n }. The reduced hyperplane arrangement H red has the same support cone as H and h i ∈ H red if and only if h i = λb, for any λ ∈ R and any b ∈ {h 1 , . . . , h i−1 }.

To a hyperplane arrangement H = {h 1 , . . . , h n } ⊆ R d we associate the polytope 

Remark 2. In polymake release 4.0 the signature was defined as the set of indices such that σ ⊆ h − i . The signature will be automatically updated for data saved in polymake 4.0 and loaded in the subsequent releases.

We will have a look at the induced fans for different support cones S H . The fan Σ H and the polytope Z H are visualized in Fig. 1 for varying S H . In each of the pictures, the support cone is indicated as the shaded area. The structure of the fan Σ H depends heavily on the support cone S H . In particular, it is possible for hyperplanes to only intersect S H trivially and thereby becoming irrelevant for Σ H . Thus, one may loose information when going from H to Σ H .

The labels at the hyperplanes in the first picture indicate which side constitutes h + , h − respectively. Using these one can read of the signatures of the single cells, for example the cell σ generated by the rays (1, 0) and (1, 2) has signature sig(σ) = {1, 2}.

An affine hyperplane arrangement is usually given by a finite set of affine hyperplanes:

The whole space R d is then subdivided along the hyperplanes

Analogously to the connection between polytopes and cones, or polyhedral complexes and fans, every affine hyperplane arrangement gives rise to a (projective) hyperplane arrangement by embedding it at height 1:

If we intersect the fan Σ Hproj with the affine hyperplane [

The support cone allows one to deal with affine hyperplanes computationally.

then the maximal cones of Σ Hproj are in one-to-one correspondence with the maximal cells of PC H aff . In particular, polymake can interpret Σ Hproj as a polyhedral complex via the embedding mentioned above, and this polyhedral complex will be exactly PC H aff .

Example 2. As a simple example, choose the following hyperplanes in R 1 :

The associated hyperplanes of H proj in R 2 are exactly those of the hyperplane arrangement from Example 1. For S H we choose the cone {x 0 ≥ 0}, then H aff will be at height one.

The induced affine hyperplane arrangement is indicated by the dots and thick line. It is one dimensional and the associated polyhedral complex PC H aff has four maximal cells. 

Hyperplane arrangements are implemented in the software polymake as a new object HyperplaneArrangement, which is derived from the already existing object VectorConfiguration. We augment the existing properties of VectorConfiguration with the following properties and methods.

1. HYPERPLANES A matrix encoding the hyperplanes as rows, this is just an override of the property VECTORS of VectorConfiguration 2. SUPPORT A polymake Cone, denoting the support S H . 3. CELL DECOMPOSITION A polymake PolyhedralFan, the cell decomposition Σ H . 4. CELL SIGNATURES A Array<Set<Int>>, the i-th set in the array contains the indices of hyperplanes evaluating positively on the i-th maximal cone of CELL DECOMPOSITION. 5. signature to cell Given a signature as Set<Int>, get the maximal cone with this signature, if it exists. 6. cell to signature Given a cell, a maximal cone of CELL DECOMPOSITION, determine its signature.

Given 

For comparing the different algorithms, we count the number of times they have to perform a convex hull computation for converting a signature to a cone. There are 2 n signatures, so we have to perform 2 n convex hull computations. As we saw in Example 1, it can happen that some hyperplanes are irrelevant, either completely or just for single cells. Furthermore, in Example 1 the fan Σ H had at most six maximal cones, however we would have to compute eight intersections with the brute force approach regardless.

Remark 3. This brute force approach is in some ways parallel to the brute force approach for computing the Minkowski sum making up Z H , by taking considering all possible sums of the endpoints of the line segments. One arrives at 2 n points whose convex hull is Z H . There are several ways to go on: either attempt a massive convex hull computation directly, or check each point individually whether it is a vertex.

Our approach is to first find a full-dimensional cone σ of Σ H and then to flip hyperplanes in order to compute its neighbors. First take a facet f of σ, then set

where h i ||f denotes that h i and f are parallel. This is the signature of the cell neighboring σ at facet f , so we can use it to determine the rays of the neighboring cell. Finding the neighbors of a cell allows one to traverse the dual graph of the fan Σ H . Taking the support cone S H into account just requires some minor tweaks, like ignoring facets of σ that are also facets of S H . By storing signatures one can avoid recomputation of cones.

To find a starting cone, one selects a generic point x from S H . A generic point will be contained in a maximal cone, this maximal cone will be

The point x may be contained in some hyperplanes, but these hyperplanes are exactly those that also contain the entire S H . Using this approach we would do one convex hull computation per maximal cone, arriving at #maxcones(Σ H ) convex hull computations.

Remark 4. As the fan Σ H is polytopal, there is a reverse search structure on it, corresponding to the edge graph of the zonotope Z H . This has already been exploited by Sleumer in [Sle99] using the software framework [Brü+99] . Reverse search allows for different kinds of parallelisation and it would be interesting to study the performance of budgeted reverse search [AJ18,AJ16] on this particular problem. Note that the dual problem, finding the vertices of Z H , is equally hard, as it is a Minkowski sum with potentially many summands. We refer the reader to [GS93] for a detailed analysis.

We conclude with a few examples which illustrate the object HyperplaneArrangement and its properties. Example 6 reports the comparison between the running times of the new algorithm implemented in polymake and the brute force algorithm to compute cell decompositions.

The following examples compute the 4! = 24 cells in the Coxeter arrangement of type A3. The 6 linear hyperplanes in the arrangements are Now we compute the 36 cells in the Linial arrangement [PS00] given by the 6 affine hyperplanes

As explained in Sect. 2.1, the support cone allows us to deal with affine hyperplanes. We transform the hyperplanes [a, b] ∈ R 4 × R in the projective arrangement H proj with hyperplanes [−b, a] and then we intersect the latter with the support cone S Hproj := {[x 0 , x 1 , . . . , x 5 ] ∈ R 5 | x 0 ≥ 0} (Fig. 2) . Example 5. This example is based on [Süß19] . Let X be a del Pezzo surface of degree 5 and [K X ] the class of the canonical divisor. The cone of effective divisors Eff(X) is spanned by ten exceptional curves [C ij ] indexed by 0 ≤ i < j ≤ 4 and characterized by [C ij ] 2 = −1 and [C ij ] · [K Y ] = −1. Applying the change of basis [C ij ] = b i + b j , described in [Süß19, Section 3], we see that the polytope P given by points in Eff(X) intersecting [K X ] with multiplicity −1 coincides with the hypersimplex Δ(2, 5). In the aforementioned article the author considers the cell decomposition of P induced by the hyperplane arrangement defined by

The decomposition is used to study the toric topology of the Grassmannian of planes in complex 5-dimensional space.

The following code allows one to compute the cell decomposition in polymake. Example 6. Let H be the hyperplane arrangement in R d given by the 2 d − 1 hyperplanes normal to 0/1-vectors. The number of maximal cones in Σ H are known up to d = 8, see entry A034997 in the Online Encyclopedia of Integer Sequences. We run polymake implementations of the BFS algorithm described above and the brute force alternative. Our results are reported in Table 1 , where we can see that the BFS algorithm performs better than the brute force approach. 

mplrs: a scalable parallel vertex/facet enumeration code

A parallel framework for reverse search using mts

The parallel search bench ZRAM and its applications

Variation of geometric invariant theory quotients

From the zonotope construction to the Minkowski addition of convex polytopes

polymake: a framework for analyzing convex polytopes

Minkowski addition of polytopes: computational complexity and applications to Gröbner bases

Deformations of Coxeter hyperplane arrangements

Output-sensitive cell enumeration in hyperplane arrangements

Toric topology of the Grassmannian of planes in C5 and the del Pezzo surface of degree 5

Lectures on Polytopes. GTM