Polyhedral Sets - Maple Help

 Polyhedral Sets

The new PolyhedralSets package brings new functionality to Maple 2015 for working with sets defined either by a set of equalities and inequalities (H-Representation), or by a set of vertices and rays (V-Representation). The added functionality lets you explore the geometric and topological properties of a set, perform standard set operations, and apply linear transformations.

$\mathrm{with}\left(\mathrm{PolyhedralSets}\right)$

 $\left[{\mathrm{AffineHull}}{,}{\mathrm{Area}}{,}{\mathrm{CharacteristicCone}}{,}{\mathrm{ConvexHull}}{,}{\mathrm{Coordinates}}{,}{\mathrm{Dimension}}{,}{\mathrm{Display}}{,}{\mathrm{DualSet}}{,}{\mathrm{Edges}}{,}{\mathrm{Equal}}{,}{\mathrm{ExampleSets}}{,}{\mathrm{Faces}}{,}{\mathrm{Facets}}{,}{\mathrm{Graph}}{,}{\mathrm{ID}}{,}{\mathrm{InteriorPoint}}{,}{\mathrm{IsBounded}}{,}{\mathrm{IsEmpty}}{,}{\mathrm{IsFace}}{,}{\mathrm{IsInInterior}}{,}{\mathrm{IsUniversalSet}}{,}{\mathrm{Length}}{,}{\mathrm{LinearTransformation}}{,}{\mathrm{LinearitySpace}}{,}{\mathrm{LocatePoint}}{,}{\mathrm{Plot}}{,}{\mathrm{PolyhedralSet}}{,}{\mathrm{PrintLevel}}{,}{\mathrm{Project}}{,}{\mathrm{Relations}}{,}{\mathrm{SplitIntoSimplices}}{,}{\mathrm{Translate}}{,}{\mathrm{Vertices}}{,}{\mathrm{VerticesAndRays}}{,}{\mathrm{Volume}}{,}{\mathrm{in}}{,}{\mathrm{intersect}}{,}{\mathrm{subset}}\right]$ (1)

Creating Sets

Polyhedral Sets can be created from a list of equalities and non-strict inequalities. Redundant relations are removed and the remaining relations are put into a canonical form that speeds up later operations.

 ${{}\begin{array}{lll}{\mathrm{Coordinates}}& {:}& \left[{x}{,}{y}{,}{z}\right]\\ {\mathrm{Relations}}& {:}& \left[{-1}{\le }{z}{,}{y}{\le }{z}{+}{2}{,}{x}{=}{-}{y}{-}{z}{+}{1}\right]\end{array}$ (1.1)

Sets can also be created from a list of vertices and rays. The package automatically prunes the list of vertices and rays to capture only the extreme vertices and rays of the set.

 ${{}\begin{array}{lll}{\mathrm{Coordinates}}& {:}& \left[{{x}}_{{1}}{,}{{x}}_{{2}}\right]\\ {\mathrm{Relations}}& {:}& \left[{-}{1}{+}{{x}}_{{2}}{\le }{{x}}_{{1}}{,}{{x}}_{{1}}{\le }{{x}}_{{2}}{+}{1}{,}{{x}}_{{1}}{\le }\frac{{{x}}_{{2}}}{{3}}{+}\frac{{1}}{{3}}\right]\end{array}$ (1.2)

The set is displayed as its H-Representation, but the conversion back to its V-Representation is simple.

$\mathrm{VerticesAndRays}\left(\mathrm{polyset}\right);$

 $\left[\left[{1}{,}{2}\right]{,}\left[{0}{,}{-}{1}\right]\right]{,}\left[\left[{-}{1}{,}{-}{1}\right]\right]$ (1.3)

The ExampleSets  subpackage streamlines the creation of common sets. See ExampleSets- NDimensions and ExampleSets- ThreeDimensions.

$\mathrm{ExampleSets}:-\mathrm{Tetrahedron}\left(\right);$

 ${{}\begin{array}{lll}{\mathrm{Coordinates}}& {:}& \left[{{x}}_{{1}}{,}{{x}}_{{2}}{,}{{x}}_{{3}}\right]\\ {\mathrm{Relations}}& {:}& \left[{-}{{x}}_{{2}}{-}{{x}}_{{3}}{-}{1}{\le }{{x}}_{{1}}{,}{{x}}_{{2}}{+}{{x}}_{{3}}{-}{1}{\le }{{x}}_{{1}}{,}{{x}}_{{1}}{\le }{-}{{x}}_{{3}}{+}{{x}}_{{2}}{+}{1}{,}{{x}}_{{1}}{\le }{{x}}_{{3}}{-}{{x}}_{{2}}{+}{1}\right]\end{array}$ (1.4)



Visualization

The sets can be rendered in 2-D or 3-D, whether they are bounded or unbounded. The style of the visualization is fully customizable for seamless integration into any webpage, document, or presentation.

 >

 >

The Structure of a Set

Finding the faces of a set allows you to explore its structure. Faces of any dimension can be obtained, from the (n - 1) faces of a set in n dimensions right down to its vertices.

$t≔\mathrm{ExampleSets}:-\mathrm{Tetrahedron}\left(\right):$

 $\left[{{}\begin{array}{lll}{\mathrm{Coordinates}}& {:}& \left[{{x}}_{{1}}{,}{{x}}_{{2}}{,}{{x}}_{{3}}\right]\\ {\mathrm{Relations}}& {:}& \left[{-1}{\le }{{x}}_{{3}}{,}{{x}}_{{3}}{\le }{{x}}_{{2}}{,}{{x}}_{{2}}{\le }{1}{,}{{x}}_{{1}}{=}{{x}}_{{3}}{-}{{x}}_{{2}}{+}{1}\right]\end{array}{,}{{}\begin{array}{lll}{\mathrm{Coordinates}}& {:}& \left[{{x}}_{{1}}{,}{{x}}_{{2}}{,}{{x}}_{{3}}\right]\\ {\mathrm{Relations}}& {:}& \left[{{x}}_{{3}}{\le }{1}{,}{-1}{\le }{{x}}_{{2}}{,}{{x}}_{{2}}{\le }{{x}}_{{3}}{,}{{x}}_{{1}}{=}{-}{{x}}_{{3}}{+}{{x}}_{{2}}{+}{1}\right]\end{array}{,}{{}\begin{array}{lll}{\mathrm{Coordinates}}& {:}& \left[{{x}}_{{1}}{,}{{x}}_{{2}}{,}{{x}}_{{3}}\right]\\ {\mathrm{Relations}}& {:}& \left[{{x}}_{{3}}{\le }{1}{,}{-}{{x}}_{{3}}{\le }{{x}}_{{2}}{,}{{x}}_{{2}}{\le }{1}{,}{{x}}_{{1}}{=}{{x}}_{{2}}{+}{{x}}_{{3}}{-}{1}\right]\end{array}{,}{{}\begin{array}{lll}{\mathrm{Coordinates}}& {:}& \left[{{x}}_{{1}}{,}{{x}}_{{2}}{,}{{x}}_{{3}}\right]\\ {\mathrm{Relations}}& {:}& \left[{-1}{\le }{{x}}_{{3}}{,}{-1}{\le }{{x}}_{{2}}{,}{{x}}_{{2}}{\le }{-}{{x}}_{{3}}{,}{{x}}_{{1}}{=}{-}{{x}}_{{2}}{-}{{x}}_{{3}}{-}{1}\right]\end{array}\right]$ (3.1)

 $\left[{{}\begin{array}{lll}{\mathrm{Coordinates}}& {:}& \left[{{x}}_{{1}}{,}{{x}}_{{2}}{,}{{x}}_{{3}}\right]\\ {\mathrm{Relations}}& {:}& \left[{{x}}_{{3}}{=}{1}{,}{{x}}_{{2}}{=}{-1}{,}{{x}}_{{1}}{=}{-1}\right]\end{array}{,}{{}\begin{array}{lll}{\mathrm{Coordinates}}& {:}& \left[{{x}}_{{1}}{,}{{x}}_{{2}}{,}{{x}}_{{3}}\right]\\ {\mathrm{Relations}}& {:}& \left[{{x}}_{{3}}{=}{-1}{,}{{x}}_{{2}}{=}{1}{,}{{x}}_{{1}}{=}{-1}\right]\end{array}{,}{{}\begin{array}{lll}{\mathrm{Coordinates}}& {:}& \left[{{x}}_{{1}}{,}{{x}}_{{2}}{,}{{x}}_{{3}}\right]\\ {\mathrm{Relations}}& {:}& \left[{{x}}_{{3}}{=}{-1}{,}{{x}}_{{2}}{=}{-1}{,}{{x}}_{{1}}{=}{1}\right]\end{array}{,}{{}\begin{array}{lll}{\mathrm{Coordinates}}& {:}& \left[{{x}}_{{1}}{,}{{x}}_{{2}}{,}{{x}}_{{3}}\right]\\ {\mathrm{Relations}}& {:}& \left[{{x}}_{{3}}{=}{1}{,}{{x}}_{{2}}{=}{1}{,}{{x}}_{{1}}{=}{1}\right]\end{array}\right]$ (3.2)

The graph of the faces is easily generated, illuminating which faces share points with which other faces. The structure of the set can then be further explored by leveraging the functionality of the GraphTheory package.

$c≔\mathrm{ExampleSets}:-\mathrm{Cube}\left(\right):$

$\mathrm{plots}:-\mathrm{display}\left(\mathrm{c_plot}\right)$

$\mathrm{GraphTheory}\left[\mathrm{Neighbors}\right]\left(\mathrm{c_graph},323\right)$

 $\left[{728}{,}{278}{,}{260}{,}{318}{,}{316}\right]$ (3.3)

Working with and Transforming Sets

The dual of a polyhedral set can be computed, whether it is bounded or not, and whether it includes the origin or not. The bounded sets that include the origin show how vertices map to faces in the dual and vice versa.

 > $\mathrm{octaprism}≔\mathrm{PolyhedralSet}\left(\left[-1\le z,z\le 1,-1\le y,y\le 1,-y-\frac{66922}{47321}\le x,-1\le x,y-\frac{66922}{47321}\le x,x\le y+\frac{66922}{47321},x\le 1,x\le -y+\frac{66922}{47321}\right]\right):$
 >
 > $\mathrm{octaprism_dual}≔\mathrm{DualSet}\left(\mathrm{octaprism}\right)$
 ${\mathrm{octaprism_dual}}{:=}{{}\begin{array}{lll}{\mathrm{Coordinates}}& {:}& \left[{x}{,}{y}{,}{z}\right]\\ {\mathrm{Relations}}& {:}& \left[{-}\frac{{47321}{}{z}}{{19601}}{-}\frac{{47321}{}{y}}{{19601}}{-}\frac{{47321}}{{19601}}{\le }{x}{,}\frac{{47321}{}{z}}{{19601}}{-}\frac{{47321}{}{y}}{{19601}}{-}\frac{{47321}}{{19601}}{\le }{x}{,}{-}{z}{-}\frac{{19601}{}{y}}{{47321}}{-}{1}{\le }{x}{,}{z}{-}\frac{{19601}{}{y}}{{47321}}{-}{1}{\le }{x}{,}{-}{z}{+}\frac{{19601}{}{y}}{{47321}}{-}{1}{\le }{x}{,}{z}{+}\frac{{19601}{}{y}}{{47321}}{-}{1}{\le }{x}{,}\frac{{47321}{}{y}}{{19601}}{-}\frac{{47321}{}{z}}{{19601}}{-}\frac{{47321}}{{19601}}{\le }{x}{,}\frac{{47321}{}{y}}{{19601}}{+}\frac{{47321}{}{z}}{{19601}}{-}\frac{{47321}}{{19601}}{\le }{x}{,}{x}{\le }\frac{{47321}{}{z}}{{19601}}{+}\frac{{47321}{}{y}}{{19601}}{+}\frac{{47321}}{{19601}}{,}{x}{\le }{-}\frac{{47321}{}{z}}{{19601}}{+}\frac{{47321}{}{y}}{{19601}}{+}\frac{{47321}}{{19601}}{,}{\cdots }{,}{\mathrm{\left(6 more constraints\right)}}\right]\end{array}$ (4.1)
 >

 >
 ${c}{:=}{{}\begin{array}{lll}{\mathrm{Coordinates}}& {:}& \left[{{x}}_{{1}}{,}{{x}}_{{2}}{,}{{x}}_{{3}}\right]\\ {\mathrm{Relations}}& {:}& \left[{1}{\le }{{x}}_{{3}}{,}{{x}}_{{3}}{\le }{3}{,}{-3}{\le }{{x}}_{{2}}{,}{{x}}_{{2}}{\le }{-1}{,}{1}{\le }{{x}}_{{1}}{,}{{x}}_{{1}}{\le }{3}\right]\end{array}$ (4.2)
 > $\mathrm{Plot}\left(c\right)$
 > $\mathrm{c_dual}≔\mathrm{DualSet}\left(c\right)$
 ${\mathrm{c_dual}}{:=}{{}\begin{array}{lll}{\mathrm{Coordinates}}& {:}& \left[{{x}}_{{1}}{,}{{x}}_{{2}}{,}{{x}}_{{3}}\right]\\ {\mathrm{Relations}}& {:}& \left[{{x}}_{{1}}{\le }{3}{}{{x}}_{{2}}{-}{{x}}_{{3}}{+}{1}{,}{{x}}_{{1}}{\le }{3}{}{{x}}_{{2}}{-}{3}{}{{x}}_{{3}}{+}{1}{,}{{x}}_{{1}}{\le }{{x}}_{{2}}{-}\frac{{{x}}_{{3}}}{{3}}{+}\frac{{1}}{{3}}{,}{{x}}_{{1}}{\le }{{x}}_{{2}}{-}{{x}}_{{3}}{+}\frac{{1}}{{3}}{,}{{x}}_{{1}}{\le }{{x}}_{{2}}{-}{3}{}{{x}}_{{3}}{+}{1}{,}{{x}}_{{1}}{\le }\frac{{{x}}_{{2}}}{{3}}{-}\frac{{{x}}_{{3}}}{{3}}{+}\frac{{1}}{{3}}{,}{{x}}_{{1}}{\le }\frac{{{x}}_{{2}}}{{3}}{-}{{x}}_{{3}}{+}\frac{{1}}{{3}}\right]\end{array}$ (4.3)
 > $\mathrm{Plot}\left(\mathrm{c_dual}\right)$

Support for linear matrix transformations, translations, and projections is included.

Linear transformations and translations (blue and green) applied to the semiregular cuboctahedron ...

The elementary set functionality, such as the intersection, convex hull, inclusion tests, and equality test provide user-friendly means of working with polyhedral sets.

Form the convex hull (green) of a cube (red) and a tetrahedron (blue)



Support for n-Dimensional Sets

Sets of higher dimensions are supported by the algorithms in the package, so that properties like the volume of a set can be calculated for any set.

 ${{}\begin{array}{lll}{\mathrm{Coordinates}}& {:}& \left[{{x}}_{{1}}{,}{{x}}_{{2}}{,}{{x}}_{{3}}{,}{{x}}_{{4}}{,}{{x}}_{{5}}\right]\\ {\mathrm{Relations}}& {:}& \left[{0}{\le }{{x}}_{{5}}{,}{0}{\le }{{x}}_{{4}}{,}{0}{\le }{{x}}_{{3}}{,}{0}{\le }{{x}}_{{2}}{,}{0}{\le }{{x}}_{{1}}{,}{{x}}_{{1}}{\le }{-}{{x}}_{{2}}{-}{{x}}_{{3}}{-}{{x}}_{{4}}{-}{{x}}_{{5}}{+}{1}\right]\end{array}$ (5.1)

$\mathrm{Volume}\left(\mathrm{s5}\right)$

 $\frac{{1}}{{120}}$ (5.2)

Likewise, the set operators can work in any dimension,

 ${\mathrm{true}}$ (5.3)

and the topological properties of sets can be explored similarly.

$\mathrm{Graph}\left(\mathrm{ExampleSets}:-\mathrm{Simplex}\left(4\right)\right)$