dualdesc

Dual description for polytopes. A wrapper around pyparma, which itself wraps ppl. Mainly for easily converting between H- and V-representations. No utilities for facet enumeration, adjacencies, etc.

Usage

Constructors

This package contains one class, Polytope. Main constructors are:

Polytope.FromHalfspaces(A, b) represents the polytope defined by all points x s.t. A @ x <= b. If there are n halfspaces and the ambient dimension is d, the shapes of these matrices are:

• A: (nu, d)
• b: (d,)

Polytope.FromGenerators(V, R) represents the polytope defined by conv(V) + nonneg(R), where conv is the convex combination of a set of points and nonneg is non-negative linear combinations of a set of points, and + is Minkowski addition.

There are also Polytope.Empty(dim: int) and Polytope.Universe(dim: int) constructors.

All constructors also take a scale > 0 (default 1e5) parameter to control quantization, since ppl uses rational arithmetic. Quantization is done as q = round(scale * x) going into ppl, and x = q / scale coming out.

Conversion

There are methods A, b = poly.get_inequalities() and V, R = poly.get_generators() which return the respective representations.

Note that PPL is lazy, and converting between representations can take a long time, so calling these methods might be slow.

Incremental construction

Incremental construction is supported via methods add_halfspace(A, b), add_point(V), and add_ray(R). All are "vectorized", i.e. they support adding a single halfspace/point/ray, or multiple.

Since these mutate, you can also copy polytopes: poly.copy().

A simple example

The example below defines an unbounded (i.e. non-null cone part) polytope with 3 facets and 2 vertices:

import numpy as np
import dualdesc as dd

M = np.array([
	[1, 0, 1], # x0        <= 1
	[0, 2, 1], #      2 x1 <= 1
	[1, 1, 1], # x0 +   x1 <= 1
], dtype = np.float64)
A = M[:,:2]
b = M[:,-1]
poly = dd.Polytope.FromHalfspaces(A, b)
V, R = poly.to_generators()
# Vertices:
# 	V = [[0.5, 0.5], [1, 0]]
# Cone:
# 	R = [[-1, 0], [0, -1]]

Why ...?

Why not pypoman?

pypoman has more features, but only supports bounded polytopes.

Why not use pyparma directly?

It doesn't have a nice interface.

Why not use pycddlib?

pycddlib has more features (like adjacency lists), but is too low level and doesn't have a nice interface.

Why not wrap pplpy instead?

I might do this at some point, since there are issues building pyparma with Cython 3.