# vertexenum: Vertex enumeration

[ geometry, gpl, library, math ] [ Propose Tags ]

Vertex enumeration of convex polytopes given by linear inequalities.

## Modules

• Geometry
• Geometry.VertexEnum

#### Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

Versions [RSS] 0.1.0.0, 0.1.1.0 CHANGELOG.md base (>=4.7 && <5), containers (>=0.6.2.1 && <0.8), hmatrix-glpk (>=0.19.0.0 && <0.20), vector-space (>=0.15 && <0.17) [details] GPL-3.0-only 2023 Stéphane Laurent Stéphane Laurent laurent_step@outlook.fr Math, Geometry https://github.com/stla/vertexenum#readme head: git clone https://github.com/stla/vertexenum by stla at 2023-11-20T08:07:49Z NixOS:0.1.1.0 1 direct, 0 indirect [details] 29 total (7 in the last 30 days) (no votes yet) [estimated by Bayesian average] λ λ λ Docs not available All reported builds failed as of 2023-11-20

[back to package description]

# vertexenum

Get the vertices of an intersection of halfspaces.

This package depends on the packages hmatrix and hmatrix-glpk; follow this link for installation instructions.

Consider the following system of linear inequalities:

$\left\{\begin{matrix} -5 & \leqslant & x & \leqslant & 4 \\ -5 & \leqslant & y & \leqslant & 3-x \\ -10 & \leqslant & z & \leqslant & 6-2x-y \end{matrix}.\right.$

Each inequality defines a halfspace. The intersection of the six halfspaces is a convex polytope. The vertexenum function can calculate the vertices of this polytope:

import Data.VectorSpace     ( AdditiveGroup((^+^), (^-^))
, VectorSpace((*^)) )
import Geometry.VertexEnum

constraints :: [Constraint Double]
constraints =
[ x .>= (-5)         -- shortcut for x .>=. cst (-5)
, x .<=  4
, y .>= (-5)
, y .<=. cst 3 ^-^ x -- we need cst here
, z .>= (-10)
, z .<=. cst 6 ^-^ 2*^x ^-^ y ]
where
x = newVar 1
y = newVar 2
z = newVar 3

vertexenum constraints Nothing


The type of the second argument of vertexenum is Maybe [Double]. If this argument is Just point, then point must be the coordinates of a point interior to the polytope. If this argument is Nothing, an interior point is automatically calculated. You can get it with the interiorPoint function. It is easy to mentally get an interior point for the above example, but in general this is not an easy problem.