IntegerHull - Maple Help

PolyhedralSets

 IntegerHull
 integer hull of a polyhedral set

 Calling Sequence IntegerHull(polyset, output=value)

Parameters

 polyset - value - (optional) either verticesandrays (default) or polyhedralset

Returns

 • The available return types are:
 – The output=verticesandrays option (default) returns a list of two elements which are the vertices and rays of the integer hull of polyset.
 – The output=polyhedralset option returns a PolyhedralSet object representing the integer hull of polyset.

Description

 • The integer hull of a convex polyhedral set is the smallest polyhedral set that contains all the integer points in the input set.
 • This command computes the integer hull of the convex polyhedral set polyset. polyset can be of any dimension greater or equal to $2$, bounded or unbounded. It returns either a list or a PolyhedralSet.

Examples

 > $\mathrm{with}\left(\mathrm{PolyhedralSets}\right):$
 > $\mathrm{ineqs}≔\left[2x+5y\le 64,20\le 7x+5y,3x-6y\le -7\right]$
 ${\mathrm{ineqs}}{≔}\left[{2}{}{x}{+}{5}{}{y}{\le }{64}{,}{20}{\le }{7}{}{x}{+}{5}{}{y}{,}{3}{}{x}{-}{6}{}{y}{\le }{-7}\right]$ (1)
 > $\mathrm{poly}≔\mathrm{PolyhedralSet}\left(\mathrm{ineqs},\left[x,y\right]\right)$
 ${\mathrm{poly}}{≔}{{}\begin{array}{lll}{\mathrm{Coordinates}}& {:}& \left[{x}{,}{y}\right]\\ {\mathrm{Relations}}& {:}& \left[{-}{x}{-}\frac{{5}{}{y}}{{7}}{\le }{-}\frac{{20}}{{7}}{,}{x}{-}{2}{}{y}{\le }{-}\frac{{7}}{{3}}{,}{x}{+}\frac{{5}{}{y}}{{2}}{\le }{32}\right]\end{array}$ (2)

By default the integer hull is returned in the form of vertices and rays.

 > $\mathrm{IntegerHull}\left(\mathrm{poly}\right)$
 $\left[\left[\left[{12}{,}{8}\right]{,}\left[{-8}{,}{16}\right]{,}\left[{-7}{,}{14}\right]{,}\left[{-5}{,}{11}\right]{,}\left[{0}{,}{4}\right]{,}\left[{1}{,}{3}\right]{,}\left[{3}{,}{3}\right]{,}\left[{11}{,}{7}\right]\right]{,}\left[\right]\right]$ (3)

You can also choose to get a PolyhedralSet instead.

 > $\mathrm{IntegerHull}\left(\mathrm{poly},\mathrm{output}=\mathrm{polyhedralset}\right)$
 ${{}\begin{array}{lll}{\mathrm{Coordinates}}& {:}& \left[{x}{,}{y}\right]\\ {\mathrm{Relations}}& {:}& \left[{-}{y}{\le }{-3}{,}{-}{x}{-}{y}{\le }{-4}{,}{-}{x}{-}\frac{{5}{}{y}}{{7}}{\le }{-}\frac{{20}}{{7}}{,}{-}{x}{-}\frac{{2}{}{y}}{{3}}{\le }{-}\frac{{7}}{{3}}{,}{-}{x}{-}\frac{{y}}{{2}}{\le }{0}{,}{x}{-}{2}{}{y}{\le }{-3}{,}{x}{-}{y}{\le }{4}{,}{x}{+}\frac{{5}{}{y}}{{2}}{\le }{32}\right]\end{array}$ (4)

The PolyhedralSet can be unbounded.

 > $\mathrm{inset}≔\mathrm{PolyhedralSet}\left(\left[\left[-\frac{7}{5},0\right],\left[\frac{13}{4},0\right],\left[-\frac{5}{3},-1\right],\left[\frac{5}{2},-1\right]\right],\left[\left[0,-1\right]\right],\left[x,y\right]\right):$
 > $\mathrm{IsBounded}\left(\mathrm{inset}\right)$
 ${\mathrm{false}}$ (5)
 > $\mathrm{IntegerHull}\left(\mathrm{inset}\right)$
 $\left[\left[\left[{-1}{,}{0}\right]{,}\left[{3}{,}{0}\right]\right]{,}\left[\left[{0}{,}{-1}\right]\right]\right]$ (6)

A 3D example.

 > $\mathrm{vertices}≔\left[\left[4,8,6\right],\left[-1,-\frac{10}{3},14\right],\left[-\frac{6}{2},8,-\frac{10}{3}\right],\left[\frac{14}{2},-\frac{22}{3},-4\right]\right]$
 ${\mathrm{vertices}}{≔}\left[\left[{4}{,}{8}{,}{6}\right]{,}\left[{-1}{,}{-}\frac{{10}}{{3}}{,}{14}\right]{,}\left[{-3}{,}{8}{,}{-}\frac{{10}}{{3}}\right]{,}\left[{7}{,}{-}\frac{{22}}{{3}}{,}{-4}\right]\right]$ (7)
 > $\mathrm{vars}≔\left[\mathrm{x1},\mathrm{x2},\mathrm{x3}\right]$
 ${\mathrm{vars}}{≔}\left[{\mathrm{x1}}{,}{\mathrm{x2}}{,}{\mathrm{x3}}\right]$ (8)
 > $\mathrm{poly3d}≔\mathrm{PolyhedralSet}\left(\mathrm{vertices},\left[\right],\mathrm{vars}\right):$
 > $\mathrm{IntegerHull}\left(\mathrm{poly3d}\right)$
 $\left[\left[\left[{-2}{,}{3}{,}{4}\right]{,}\left[{-2}{,}{4}{,}{3}\right]{,}\left[{-2}{,}{6}{,}{-2}\right]{,}\left[{-2}{,}{8}{,}{-2}\right]{,}\left[{-1}{,}{-2}{,}{12}\right]{,}\left[{-1}{,}{5}{,}{-3}\right]{,}\left[{0}{,}{-3}{,}{10}\right]{,}\left[{0}{,}{-3}{,}{11}\right]{,}\left[{0}{,}{-2}{,}{12}\right]{,}\left[{0}{,}{-1}{,}{12}\right]{,}\left[{0}{,}{0}{,}{11}\right]{,}\left[{1}{,}{-4}{,}{9}\right]{,}\left[{1}{,}{-2}{,}{10}\right]{,}\left[{2}{,}{1}{,}{-3}\right]{,}\left[{3}{,}{-5}{,}{5}\right]{,}\left[{3}{,}{-2}{,}{-2}\right]{,}\left[{3}{,}{-1}{,}{6}\right]{,}\left[{4}{,}{-5}{,}{1}\right]{,}\left[{4}{,}{-3}{,}{-3}\right]{,}\left[{4}{,}{8}{,}{6}\right]{,}\left[{5}{,}{-6}{,}{0}\right]{,}\left[{5}{,}{-4}{,}{1}\right]{,}\left[{5}{,}{1}{,}{1}\right]{,}\left[{6}{,}{-6}{,}{-3}\right]{,}\left[{6}{,}{-6}{,}{-2}\right]{,}\left[{6}{,}{-5}{,}{-3}\right]{,}\left[{6}{,}{-3}{,}{-1}\right]\right]{,}\left[\right]\right]$ (9)

References

 Marc Moreno Maza, and Linxiao Wang. On the Pseudo-Periodicity of the Integer Hull of Parametric Convex Polygons. International Workshop on Computer Algebra in Scientific Computing 2021. Springer LNCS 12865, 2021.
 Marc Moreno Maza and Linxiao Wang. Computing the Integer Hull of Convex Polyhedral Sets. International Workshop on Computer Algebra in Scientific Computing 2022. Springer LNCS 13366, 2022.

Compatibility

 • The PolyhedralSets[IntegerHull] command was introduced in Maple 2022.