vertexenum: Vertex enumeration

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain] [Publish]

Warnings:

Vertex enumeration of convex polytopes.


[Skip to Readme]

Properties

Versions 0.1.0.0, 0.1.0.0, 0.1.1.0, 1.0.0.0
Change log CHANGELOG.md
Dependencies 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]
License GPL-3.0-only
Copyright 2023 Stéphane Laurent
Author Stéphane Laurent
Maintainer laurent_step@outlook.fr
Category Math, Geometry
Home page https://github.com/stla/vertexenum#readme
Source repo head: git clone https://github.com/stla/vertexenum
Uploaded by stla at 2023-11-18T09:37:13Z

Modules

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


Readme for vertexenum-0.1.0.0

[back to package description]

vertexenum

Stack

Get the vertices of an intersection of halfspaces.


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.Ratio           ( (%) )
import Data.VectorSpace     ( AdditiveGroup((^+^), (^-^))
                            , VectorSpace((*^)) )
import Geometry.VertexEnum

constraints :: [Constraint]
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.