View in EDS HTML Full Text PDF Full Text

A Complete Description of Cones and Polytopes Including Hypervolumes of All Facets of a Polytope

Saved in:
Bibliographic Details
Title: A Complete Description of Cones and Polytopes Including Hypervolumes of All Facets of a Polytope
Language: English
Authors: Jubete, F., Castillo, E.
Source: International Journal of Mathematical Education in Science & Technology. Jan 2007 38(1):85-102.
Availability: Taylor & Francis, Ltd. 325 Chestnut Street Suite 800, Philadelphia, PA 19106. Tel: 800-354-1420; Fax: 215-625-2940; Web site: http://www.tandf.co.uk/journals/default.html
Peer Reviewed: Y
Page Count: 18
Publication Date: 2007
Document Type: Journal Articles
Reports - Descriptive
Descriptors: Algebra, Geometric Concepts, Mathematical Formulas, Mathematical Logic, Background, Illustrations, Scientific Methodology, Mathematics Education
ISSN: 0020-739X
Abstract: In this paper methods and algorithms for identifying the main elements (edges and facets of any dimension) of a cone and a polytope, and calculating the corresponding hypervolumes are presented. The cones and polytopes are supposed to be given as the non-negative linear combination and the convex hull generated by a, not necessarily minimal, set of vectors (points), respectively, and they can be degenerated (of a dimension smaller than that of the proper space in which they are contained). First a minimum set of generators (edges and vertices) are obtained by eliminating the redundant vectors. In the case of cones, the linear space basis and the minimal cone generators are obtained. Second the set of all facets of any dimension are identified. Finally, an algorithm for obtaining the associated hypervolumes of any dimension, i.e. the length of its edges, the areas of its faces of dimension two, and the hypervolumes of its facets of any dimension, is introduced. The proposed formula leads to a recursion that gives the hypervolumes of dimension "n" as a function of other hypervolumes of dimension "n"-1. Examples are used to illustrate the proposed methods and algorithms. (Contains 4 tables and 1 figure.)
Abstractor: Author
Number of References: 22
Entry Date: 2007
Access URL: https://taylorandfrancis.metapress.com/link.asp?id=R4K5863536K1UK80
Accession Number: EJ753951
Database: ERIC
Full text is not displayed to guests.
FullText Links:
  – Type: pdflink
    Url: https://content.ebscohost.com/cds/retrieve?content=AQICAHj0k_4E0hTGH8RJwT4gCJyBsGNe_WN95AvKlDbXJGqwxwFYn7D3pfjmeHAB3suLqtTHAAAA4jCB3wYJKoZIhvcNAQcGoIHRMIHOAgEAMIHIBgkqhkiG9w0BBwEwHgYJYIZIAWUDBAEuMBEEDKKNNQvBojnHZzxnwQIBEICBmqZZyhVU3Nm6hNPXm0c14rcBDXktimNAHPPmqNyHJLfvlnC-yYfRK1c8NWO9baWuC-jPA8vmPn1qEJhB5YA9a5fh7np37-y55mUZWyRrhLqbqybFAQQyYGWA8NgPp-wfCEBdwHkTCKeevNWQ4Utc1VlAtYNTkSMbdWG0vX33kFkX2qgD-L2lL2WMH8ppWgLpiwVYflxSu-KRos4=
Text:
  Availability: 1
  Value: <anid>AN0023219924;imt15jan.07;2019Feb25.13:23;v2.2.500</anid> <title id="AN0023219924-1">A complete description of cones and polytopes including hypervolumes of all facets of a polytope. </title> <sbt id="AN0023219924-2">1. Introduction</sbt> <p>In this paper methods and algorithms for identifying the main elements (edges and facets of any dimension) of a cone and a polytope, and calculating the corresponding hypervolumes are presented. The cones and polytopes are supposed to be given as the non-negative linear combination and the convex hull generated by a, not necessarily minimal, set of vectors (points), respectively, and they can be degenerated (of a dimension smaller that that of the proper space in which they are contained). First a minimum set of generators (edges and vertices) are obtained by eliminating the redundant vectors. In the case of cones, the linear space basis and the minimal cone generators are obtained. Second the set of all facets of any dimension are identified. Finally, an algorithm for obtaining the associated hypervolumes of any dimension, i.e. the length of its edges, the areas of its faces of dimension two, and the hypervolumes of its facets of any dimension, is introduced. The proposed formula leads to a recursion that gives the hypervolumes of dimension n as a function of other hypervolumes of dimension n − 1. Examples are used to illustrate the proposed methods and algorithms.</p> <p>Let <emph>X</emph> be a set of <emph>m</emph> vectors (points) in the <emph>n</emph>-dimensional Euclidean space , and consider the cone and the polytope (convex hull) generated by the vectors in <emph>X</emph>. Then, we can ask the following questions:</p> <p></p> <ulist> <item> 1. What is the minimum set of generators and edges of this cone?</item> <p></p> <item> 2. What are the vertices (minimum set of generators) of this polytope?</item> <p></p> <item> 3. What are the facets of any dimension of the cone?</item> <p></p> <item> 4. What are the facets of any dimension of the polytope?</item> <p></p> <item> 5. What is the hypervolume of the polytope?</item> <p></p> <item> 6. What are the hypervolumes associated with each of the polytope facets of any dimension?</item> </ulist> <p>The first four problems have been treated in the past (see, for example, Minkowski [<reflink idref="bib1" id="ref1">1</reflink>]). However, his advances were clearly insufficient. Only after 1953, when Motzkin, Raiffa, Thompson, and Thrall [<reflink idref="bib2" id="ref2">2</reflink>] published the method of double description, which was later improved by Chernikova [<reflink idref="bib3" id="ref3">3</reflink>] and Greenberg [<reflink idref="bib4" id="ref4">4</reflink>], were important advances made. Today we have several methods for solving them. They can be seen, for example, in Dyer [<reflink idref="bib5" id="ref5">5</reflink>], Fukuda and Prodon [<reflink idref="bib6" id="ref6">6</reflink>], Avis and Fukuda [<reflink idref="bib7" id="ref7">7</reflink>], Chazelle [<reflink idref="bib8" id="ref8">8</reflink>], Pillers [<reflink idref="bib9" id="ref9">9</reflink>], Avis, Bremner, and Seidel [<reflink idref="bib10" id="ref10">10</reflink>], Bremner, Fukuda, and Marzetta [<reflink idref="bib11" id="ref11">11</reflink>] and Fukuda, Liebling, and Margot [<reflink idref="bib12" id="ref12">12</reflink>].</p> <p>A nice description of the existing methods for solving the last two problems in the above list, i.e. calculating the hypervolume of a polytope and its facets of all dimensions, together with a comparison of some existing codes for its practical calculation is given in Büeler, Enge, and Fukuda [<reflink idref="bib13" id="ref13">13</reflink>], and some interesting methods are described in Laserre [<reflink idref="bib14" id="ref14">14</reflink>] and Lawrence [<reflink idref="bib15" id="ref15">15</reflink>]. For some of these methods to have a practical application (see Castillo <emph>et al</emph>. [<reflink idref="bib21" id="ref16">21</reflink>], [<reflink idref="bib22" id="ref17">22</reflink>]), an efficient algorithm for obtaining dual cones becomes necessary. However existing methods present some limitations as, for example, requiring non-degenerate problems, non-redundant sets of inequalities, pointed cones, etc.</p> <p>In this paper we answer all these questions giving algorithms and methods for solving the convex hull computation problem and the vertex and facet enumeration problems, based on the Γ-algorithm, introduced by Castillo, Cobo, Jubete and Pruneda [[<reflink idref="bib16" id="ref18">16</reflink>]], for obtaining the dual cone of a given cone. This algorithm has important properties, that have been shown to be very useful to solve a long list of problems in linear algebra, such as writing a cone in one of its minimal representations, solving homogeneous and complete systems of linear inequalities, deciding whether or not a system of linear inequalities is compatible, determining whether or not a vector belongs to a cone or polytope, finding the intersections of cones or polytopes, etc.</p> <p>The main contributions of the paper are the methods to obtain all facets of any dimension of a cone or polytope and to calculate the corresponding hypervolumes, based on the Γ-algorithm. In this paper we show that this algorithm can also be used as the main tool to solve the above list of problems. The main advantage of this algorithm with respect to existing ones is that it deals separately with the two main components of the primal and the dual cones, their linear space components and their pure cone (acute cone) components. This allows one to start the process, working with degenerated problems (the origin need not to be an extreme point), and dealing with redundant constraints or generators without any problem. In other words, the algorithm does not care about degenerated or non-degenerated problems, and redundant or non-redundant constraints of generators.</p> <p>The paper is structured as follows. In section 2 we introduce some necessary background and notation. In section 3 the Γ-algorithm is described. In section 4 we obtain the minimal representations of cones and polytopes, defined in terms of its edges and vertices, respectively. In section 5, we give methods for finding the facets of any dimension of cones and polytopes. In section 6 we show how to test whether or not a vector belongs to the boundary of a cone or to its interior. In section 7 we deal with the problem of obtaining the hypervolumes of any dimension. Finally, some conclusions are given in section 8.</p> <hd id="AN0023219924-3">2. Some necessary background and notation</hd> <p>Before discussing how vertices, edges, faces, and facets of cones and polytopes, and hypervolumes of polytopes are obtained, some elemental concepts and the basic notation need to be introduced.</p> <hd id="AN0023219924-4">Definition 1 (Polyhedral convex cone)</hd> <p> <emph>Let <bold>A</bold> be a matrix, and</emph> {<bold>a</bold><subs>1</subs>, ..., <bold>a</bold><subs><emph>m</emph></subs>} <emph>be its column vectors. The set</emph></p> <p>Graph</p> <p> <emph>of all nonnegative linear combinations of the column vectors of</emph> <bold>A</bold> <emph>is known as the polyhedral convex cone generated by</emph> <bold>a</bold> <subs>1</subs>, ..., <bold>a</bold><subs><emph>m</emph></subs> (<emph>its generators</emph>).</p> <p>In this paper we use the notation <bold>A</bold> to refer to the set {<bold>a</bold><subs>1</subs>, ..., <bold>a</bold><subs><emph>m</emph></subs>} and also to the matrix (<bold>a</bold><subs>1</subs>, ..., <bold>a</bold><subs><emph>m</emph></subs>), whose columns are the elements of this set.</p> <p>We denote the set of all nonnegative linear combinations of vectors in <bold>A</bold> by <bold>A</bold><subs>π</subs>. Similarly, we denote <bold>A</bold><subs>ρ</subs> and <bold>A</bold><subs>σ</subs> the linear space and the set of all vectors generated by positive linear combinations of the column vectors of <bold>A</bold>, respectively. In this paper the Greek letters π, ρ and σ are used for nonnegative real numbers, real numbers, and positive real numbers, respectively, i.e. , ρ ∈ , and .</p> <p>In the following, for simplicity, we shall refer to polyhedral convex cones as cones.</p> <hd id="AN0023219924-5">Definition 2 (Acute cone)</hd> <p> <emph>A cone</emph> <bold>A</bold> <subs>π</subs> <emph>is said to be acute if</emph>.</p> <p>In an acute cone the linear space component is absent.</p> <hd id="AN0023219924-6">Definition 3 (General form of a polyhedral convex cone)</hd> <p> <emph>Any cone</emph> <bold>A</bold> <subs>π</subs> <emph>can be written as</emph> </p> <p>Graph</p> <p> <emph>where</emph> <bold>B</bold> <subs>ρ</subs> <emph>is a linear space and</emph> <bold>C</bold> <subs>π</subs> <emph>is an acute cone. This is called the general form of the cone.</emph> </p> <hd id="AN0023219924-7">Definition 4 (Minimal Representation of a Cone)</hd> <p> <emph>A general form</emph> <bold>B</bold> <subs>ρ</subs> +<bold>C</bold><subs>π</subs><emph>of a cone</emph><bold>A</bold><subs>π</subs><emph>is said to be a minimal representation of</emph><bold>A</bold><subs>π</subs> iff <emph>the number of columns</emph> (<emph>generators</emph>) <emph>of matrices</emph><bold>B</bold><emph>and</emph><bold>C</bold><emph>cannot be reduced.</emph></p> <hd id="AN0023219924-8">Definition 5 (Nonpositive dual or polar cone)</hd> <p> <emph>Let</emph> <bold>A</bold> <subs>π</subs> <emph>be a cone in</emph> <emph>and</emph> <bold>a</bold> <subs>1</subs>, ..., <bold>a</bold><subs><emph>m</emph></subs><emph>its generators. The non-positive dual</emph><emph>of</emph><bold>A</bold><subs>π</subs><emph>is defined as the set</emph></p> <p>Graph</p> <p> <emph>that is, the set of all vectors such that their dot products by all vectors in</emph> <bold>A</bold> <subs>π</subs> <emph>are nonpositive</emph>.</p> <p>In this paper the superindex <emph>p</emph> is used to refer to the polar or dual cone.</p> <p>Minkowski [<reflink idref="bib1" id="ref19">1</reflink>] proved that is a cone too, which is known as the polar cone. Dual cones are the key concept to solve the problems stated in this paper.</p> <hd id="AN0023219924-9">Definition 6 (Interior of a cone)</hd> <p> <emph>A vector</emph> <bold>A</bold> <emph>is interior to a cone</emph> <bold>A</bold> <subs>π</subs> <emph>iff</emph> <bold>a</bold> ∈ <bold>A</bold><subs>σ</subs>. <emph>The set of interior vectors of a cone is called the interior of a cone and is denoted as</emph>.</p> <hd id="AN0023219924-10">Definition 7 (Boundary of a cone)</hd> <p> <emph>The boundary of a cone</emph> <bold>A</bold> <subs>π</subs>, <emph>denoted as</emph>, <emph>is the set of all cone vectors that are not interior to it.</emph></p> <hd id="AN0023219924-11">Definition 8 (Edge of a cone)</hd> <p> <emph>A vector</emph> <bold>A</bold> <emph>of a cone</emph> <bold>A</bold> <subs>π</subs>, <emph>is said to be an edge of the cone</emph><bold>A</bold><subs>π</subs><emph>iff there exists a minimal set of generators of the</emph><bold>A</bold><subs>π</subs><emph>containing</emph><bold>A</bold>.</p> <p>Jubete [<reflink idref="bib19" id="ref20">19</reflink>] shows that an edge can also be defined as follows.</p> <hd id="AN0023219924-12">Definition 9 (Alternative definition of edge of a cone)</hd> <p> <emph>In a cone</emph> <bold>A</bold> <subs>π</subs>≡(<bold>a</bold><subs>1</subs>,<bold>a</bold><subs>2</subs>, ... ,<bold>a</bold><subs><emph>r</emph></subs>)<subs>π</subs>, <emph>a generator</emph><bold>a</bold><subs><emph>i</emph></subs><emph>is an edge iff</emph></p> <p>Graph</p> <p> <emph>The set of edges of the cone</emph> <bold>A</bold> <subs>π</subs> <emph>is denoted as</emph> <bold>A</bold> <sups>e</sups>.</p> <hd id="AN0023219924-13">Definition 10 (Main face of a cone)</hd> <p> <emph>Let</emph> <bold>A</bold> <subs>π</subs> <emph>be a cone and</emph> <emph>be its dual in one of its minimal forms. The cone generated by the set of vectors</emph> </p> <p>Graph</p> <p> <emph>is called the main face of the cone associated with</emph> <bold>w</bold> <subs> <emph>j</emph> </subs>.</p> <p>According to its definition, the number of main faces in a cone coincides with the number of minimal generators of <bold>W</bold><subs>π</subs>.</p> <p>Associated with the set <emph>A</emph>(<bold>w</bold><subs>j</subs>) is the set</p> <p>Graph</p> <p>where <emph>A</emph>(<bold>w</bold><subs>j</subs>) is a set of vectors and <emph>I<subs>j</subs></emph> (set of indices of <bold>A</bold>-vectors such that they are orthogonal to <bold>w</bold><subs><emph>j</emph></subs>) is the set of corresponding indices.</p> <hd id="AN0023219924-14">Definition 11 (Polytope)</hd> <p> <emph>Let</emph> <bold>Q</bold> = {<bold>q</bold><subs>1</subs>, ...,<bold>q</bold><subs><emph>k</emph></subs>}. <emph>The set</emph></p> <p>Graph</p> <p> <emph>of all linear convex combinations of the column vectors of</emph> <bold>Q</bold> <emph>is known as a polytope or the convex hull generated by</emph> {<bold>q</bold><subs>1</subs>, ... ,<bold>q</bold><subs><emph>k</emph></subs>}.</p> <p>The Greek letter λ is used in this paper to refer to coefficients of linear convex combinations, i.e., nonnegative and adding up to one.</p> <p>In practical applications it is important to obtain minimal sets of generators, of linear spaces, cones and polytopes. It is well known how a basis (minimal set of generators) of a linear space can be obtained. In section 4 we will see how a minimal set of generators for a cone and a polytope can be obtained.</p> <p>To work with polytopes, we replace our Euclidean space by another Euclidean space. In this way, polytopes in are converted to cones in , thus making the cone tools available to polytopes. However, at the end, we need to return to our initial polytope in the Euclidean space .</p> <p>Consequently, the following definition is needed.</p> <hd id="AN0023219924-15">Definition 12 (Cone associated with a polytope)</hd> <p> <emph>Given the polytope</emph> <bold>Q</bold> <subs>λ</subs> = (<bold>q</bold><subs>1</subs>, <bold>q</bold><subs>2</subs>, ..., <bold>q</bold><subs><emph>k</emph></subs>)<subs>λ</subs>, <emph>the cone</emph><emph>is called the cone associated with the polytope</emph><bold>Q</bold><subs>λ</subs>.</p> <p>Thus, we have</p> <p>Graph</p> <p>The cone <bold>Q</bold><subs>π</subs> is acute because −<bold>q</bold><subs><emph>i</emph></subs> has a negative last component and all the generators in <bold>Q</bold><subs>π</subs> have positive last components. Thus, −<bold>q</bold><subs><emph>i</emph></subs> ∉<bold>Q</bold><subs>π</subs>.</p> <p>The cone associated with a polytope allows defining the main elements of polytopes by referring to the corresponding cone elements, i.e., the edges of <bold>A</bold><subs>π</subs> coincide with the vertices of <bold>A</bold><subs>λ</subs> and the main faces of <bold>A</bold><subs>π</subs> coincide with the main faces of <bold>A</bold><subs>λ</subs>.</p> <hd id="AN0023219924-16">Definition 13 (Vertex of a polytype)</hd> <p> <emph>A vector</emph> <bold>Q</bold> <emph>of a polytope</emph> <bold>Q</bold> <subs>λ</subs> <emph>is called a vertex of</emph> <bold>Q</bold> <subs>λ</subs> <emph>iff</emph> <emph>is an edge of its associated cone</emph>.</p> <p>Similarly, the edges of a polytope are the intersections of the main faces of the associated cone with the hyperplane <emph>x</emph><subs><emph>n</emph>+1</subs>=1.</p> <p>We define the elements of a polytope <bold>Q</bold><subs>λ</subs> in a similar form, i.e., , since .</p> <hd id="AN0023219924-17">3. The Γ-algorithm for obtaining the dual of a cone</hd> <p>In this section we describe the Γ-algorithm in detail (see Castillo and Jubete [<reflink idref="bib17" id="ref21">17</reflink>]).</p> <hd1 id="AN0023219924-18">Algorithm 1 (Dual cone of a given cone)</hd1> <p></p> <ulist> <item> <bold> • _B_Input:</bold> A cone defined by a non-necessarily minimal set of generators <bold>A</bold> = {<bold>a</bold><subs>1</subs>, ..., <bold>a</bold><subs><emph>m</emph></subs>} in that is partitioned in two sets: <bold>B</bold> and <bold>C</bold>, such that the cone be in standard form <bold>A</bold><subs>π</subs> = <bold>B</bold><subs>ρ</subs> + <bold>C</bold><subs>π</subs>.</item> <p></p> <item> <bold> • _B_Output:</bold> The dual cone in one of its minimal representations .</item> </ulist> <hd1 id="AN0023219924-19">Initialization:</hd1> <p></p> <ulist> <item> <bold> • Since at iteration _I_h_i_ we look for a minimal set of generators of the dual cone generated by {_B_a</bold> <subs>1</subs>, ..., <bold>a</bold><subs><emph>h</emph></subs>} in the form , the matrix <bold>U</bold><sups>h</sups> of the generators of at iteration <emph>h</emph>, will be partitioned as (<bold>V</bold><sups>h</sups>, <bold>W</bold><sups>h</sups>), where the columns of <bold>V</bold><sups><emph>h</emph></sups> and <bold>W</bold><sups><emph>h</emph></sups> are the linear space and the acute cone generators of the corresponding dual cone, respectively.</item> <p></p> <item> <bold> Initially, i.e. when no _B_A</bold> vectors have been considered yet, the dual cone is , where <bold>I</bold><subs><emph>n</emph></subs> is the identity matrix of dimension <emph>n</emph>. Then, we let <bold>V</bold><sups>1</sups> = <bold>I</bold><subs><emph>n</emph></subs>, <bold>W</bold><sups>1</sups> = ∅, and <bold>U</bold><sups>1</sups> = (<bold>V</bold><sups>1</sups>, <bold>W</bold><sups>1</sups>).</item> <p></p> <item> <bold> • Since for minimal representation purposes, each vector in _B_U</bold> <sups>h</sups> will be assigned at the end of iteration <emph>h</emph> the set</item> <p></p> </ulist> <p>• </p> <p>Graph</p> <p></p> <ulist> <item> we initialize the set to empty sets, for <emph>j</emph> = 1,2, ..., <emph>n</emph>, and let <emph>h</emph> = 1 (first iteration).</item> </ulist> <p> <bold>Regular process:</bold> </p> <hd id="AN0023219924-20">Step 1:</hd> <p> <bold>Calculate the dot products.</bold> Calculate .</p> <hd id="AN0023219924-21">Step 2:</hd> <p> <bold>Look for the pivot.</bold> Find a column <bold>v</bold><subs><emph>p</emph></subs> (called a pivot column) in <bold>V</bold><sups><emph>h</emph></sups> such that .</p> <hd id="AN0023219924-22">Step 3:</hd> <p>Test for <emph>Γ</emph><emph><subs>I</subs></emph> or processes. If no pivot has been found, go to <bold>Process II</bold> (Step 5). Otherwise go to <bold>Process I</bold> (Step 4).</p> <hd id="AN0023219924-23">Step 4:</hd> <p> <bold>Process I.</bold> Normalize the pivot column by dividing it by . Perform the pivoting process by letting for all <emph>j</emph> ≠ <emph>p</emph>;<emph>i</emph> = 1,2, ..., <emph>n</emph>. Append the index <emph>h</emph> to the sets for all <emph>j</emph> ≠ <emph>p</emph>. If <bold>a</bold><subs><emph>h</emph></subs> ∈ <bold>B</bold>, remove vector from <bold>V</bold><sups><emph>h</emph></sups> and go to Step 6. Otherwise, remove the pivot column from <bold>V</bold><sups><emph>h</emph></sups>, and append it to <bold>W</bold><sups><emph>h</emph></sups>. Then, go to Step 6.</p> <hd id="AN0023219924-24">Step 5:</hd> <p>Process II. Append to the index <emph>h</emph> for all <emph>j</emph> such that  = 0.</p> <p>For all <bold>w</bold><subs><emph>j</emph></subs> ∈ <bold>W</bold><sups><emph>h</emph></sups> such that divide <bold>w</bold><subs><emph>j</emph></subs> by . Consider the set of vectors</p> <p>Graph</p> <p>Assign the vectors in <emph>Z</emph> the sets , and select from <emph>Z</emph> a maximal subset <emph>Z</emph>*⊂<emph>Z</emph> of vectors <bold>w</bold><subs><emph>k</emph>(<emph>i,j</emph>)</subs> such that and , for all <bold>w</bold><subs><emph>s</emph></subs> such that  = 0.</p> <p>Remove from <bold>W</bold><sups><emph>h</emph></sups> all <bold>w</bold><subs><emph>j</emph></subs> such that  > 0. If <bold>a</bold><subs><emph>h</emph></subs> ∈ <bold>B</bold> remove from <bold>W</bold><sups><emph>h</emph></sups> all vectors <bold>w</bold> such that . Append to <bold>W</bold><sups><emph>h</emph></sups> all vectors of <emph>Z</emph>*.</p> <hd id="AN0023219924-25">Step 6:</hd> <p>If <emph>h</emph> < <emph>m</emph>, let <emph>h</emph> = <emph>h</emph>+1 and go to Step 1; otherwise, return matrices <bold>V</bold><sups><emph>h</emph></sups> and <bold>W</bold><sups><emph>h</emph></sups>, and exit.</p> <hd id="AN0023219924-26">Example 1 (Γ-algorithm)</hd> <p>Consider the cone <bold>A</bold><subs>π</subs>, where</p> <p>Graph</p> <p>In table 1 the different steps of the Γ-algorithm are illustrated. Each tableau contains the vector <bold>a</bold><subs><emph>h</emph></subs> in its first column, the dot products in the indicated row, the sets of orthogonal indices <emph>I<subs>j</subs></emph>, in the last rows, and the column vectors that generate the dual cone to the cone generated by {<bold>a</bold><subs>1</subs>,<bold>a</bold><subs>2</subs>, ... ,<bold>a</bold><subs><emph>h</emph>−1</subs>}. It also contains information about the sets <bold>V</bold> and <bold>w</bold>, i.e. which vectors belong to <bold>V</bold> and which ones belong to <bold>w</bold>. To facilitate the identification of pivot columns, they have been boldfaced.</p> <p>Table 1. Illustration of the Γ-algorithm, showing the generators a1, a2,..., a9 of the cone which dual cone is looked for, the dot products, the IA(u) sets, and the transformations associated with the different steps. Pivot columns are boldfaced.</p> <p> <ephtml> <table><thead valign="middle"><tr><td><bold>Phase 1</bold> (<italic>h</italic> = 1)</td><td><bold>Phase 2</bold> (<italic>h</italic> = 2)</td><td><bold>Phase 3</bold> (<italic>h</italic> = 3)</td><td><bold>Phase 4</bold> (<italic>h</italic> = 4)</td><td><bold>Phase 5</bold> (<italic>h</italic> = 5)</td></tr><tr><td><bold>a</bold><sub>1</sub></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0047.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0048.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0049.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0050.gif" /></p></td><td><bold>a</bold><sub>2</sub></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0051.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0052.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0053.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0054.gif" /></p></td><td><bold>a</bold><sub>3</sub></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0055.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0056.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0057.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0058.gif" /></p></td><td><bold>a</bold><sub>4</sub></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0059.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0060.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0061.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0062.gif" /></p></td><td><bold>a</bold><sub>5</sub></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0063.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0064.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0065.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0066.gif" /></p></td></tr></thead><tbody valign="bottom"><tr><td>0</td><td>1</td><td>0</td><td>0</td><td><bold>0</bold></td><td>1</td><td>0</td><td><bold>0</bold></td><td>0</td><td>1</td><td>3</td><td>0</td><td>0</td><td>0</td><td><bold>1</bold></td><td>1</td><td>1/3</td><td>0</td><td>−1/3</td><td><bold>0</bold></td><td>0</td><td>1/3</td><td>0</td><td>−1/3</td><td>0</td></tr><tr><td>0</td><td>0</td><td>1</td><td>0</td><td><bold>0</bold></td><td>1</td><td>0</td><td><bold>1</bold></td><td>0</td><td>0</td><td>0</td><td>1</td><td>−1</td><td>−2</td><td>−<bold>1</bold></td><td>1</td><td>2/3</td><td>−1</td><td>1/3</td><td>−2</td><td>1</td><td>2/3</td><td>1</td><td>1/3</td><td>−2</td></tr><tr><td>0</td><td>0</td><td>0</td><td>1</td><td><bold>0</bold></td><td>2</td><td>0</td><td><bold>0</bold></td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td><bold>0</bold></td><td>1</td><td>0</td><td>0</td><td>0</td><td><bold>1</bold></td><td>2</td><td>0</td><td>−1</td><td>0</td><td>1</td></tr><tr><td>1</td><td>0</td><td>0</td><td>0</td><td><bold>1</bold></td><td>1</td><td>−1</td><td><bold>0</bold></td><td>0</td><td>0</td><td>1</td><td>−1</td><td>0</td><td>0</td><td><bold>0</bold></td><td>1</td><td>−1</td><td>0</td><td>0</td><td><bold>0</bold></td><td>1</td><td>−1</td><td>0</td><td>0</td><td>0</td></tr><tr><td><bold>t</bold><sup>1</sup></td><td>0</td><td>0</td><td>0</td><td><bold>1</bold></td><td><bold>t</bold><sup>2</sup></td><td>−1</td><td><bold>1</bold></td><td>2</td><td>1</td><td><bold>t</bold><sup>3</sup></td><td>−1</td><td>0</td><td>0</td><td><bold>3</bold></td><td><bold>t</bold><sup>4</sup></td><td>0</td><td>−1</td><td>0</td><td>−1</td><td><bold>t</bold><sup>5</sup></td><td>−1/3</td><td>−1</td><td>1/3</td><td>0</td></tr><tr><td><italic>I<sub>j</sub></italic></td><td>1</td><td>1</td><td>1</td><td /><td><italic>I<sub>j</sub></italic></td><td /><td>1</td><td>1</td><td>1</td><td><italic>I<sub>j</sub></italic></td><td>2</td><td>1</td><td>1</td><td>1</td><td><italic>I<sub>j</sub></italic></td><td>2</td><td>1</td><td>1</td><td>1</td><td><italic>I<sub>j</sub></italic></td><td>2</td><td>1</td><td>1</td><td>1</td></tr><tr><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td>3</td><td>2</td><td>2</td><td /><td>3</td><td>3</td><td>2</td><td>2</td><td /><td>3</td><td>3</td><td>2</td><td>2</td></tr><tr><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td>3</td><td /><td /><td>4</td><td /><td>4</td><td>3</td><td /><td>4</td><td>4</td><td>4</td><td>3</td></tr><tr><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td /><td>5</td></tr></tbody></table> </ephtml> </p> <p>Table 1. Illustration of the Γ-algorithm, showing the generators a1, a2,..., a9 of the cone which dual cone is looked for, the dot products, the IA(u) sets, and the transformations associated with the different steps. Pivot columns are boldfaced.</p> <p> <ephtml> <table><thead valign="middle"><tr><td><bold>Phase 6</bold> (<italic>h</italic> = 6)</td><td><bold>Phase 7</bold> (<italic>h</italic> = 7)</td><td><bold>Phase 8</bold> (<italic>h</italic> = 8)</td></tr><tr><td><bold>a</bold><sub>6</sub></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0067.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0068.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0069.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0070.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0071.gif" /></p></td><td><bold>a</bold><sub>7</sub></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0072.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0073.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0074.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0075.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0076.gif" /></p></td><td><bold>a</bold><sub>8</sub></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0077.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0078.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0079.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0080.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0081.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0082.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0083.gif" /></p></td></tr></thead><tbody valign="bottom"><tr><td>3</td><td>0</td><td>1/3</td><td>0</td><td>0</td><td>−1/3</td><td>0</td><td>0</td><td>4/3</td><td>0</td><td>0</td><td>−4/3</td><td>1</td><td>0</td><td>4/3</td><td>0</td><td>0</td><td>−4</td><td>4/9</td><td>−8/3</td></tr><tr><td>2</td><td>−2</td><td>2/3</td><td>1</td><td>1/3</td><td>2/3</td><td>2</td><td>−2</td><td>0</td><td>0</td><td>2/3</td><td>2</td><td>2</td><td>−2</td><td>0</td><td>0</td><td>4/3</td><td>0</td><td>16/9</td><td>4</td></tr><tr><td>0</td><td>1</td><td>0</td><td>−1</td><td>0</td><td>−1/3</td><td>1</td><td>1</td><td>4/3</td><td>−2</td><td>1/3</td><td>−1</td><td>3</td><td>1</td><td>4/3</td><td>−2</td><td>4/3</td><td>0</td><td>4/3</td><td>−8</td></tr><tr><td>1</td><td>0</td><td>−1</td><td>0</td><td>−1/3</td><td>0</td><td>1</td><td>0</td><td>−4</td><td>0</td><td>−4/3</td><td>0</td><td>1</td><td>0</td><td>−4</td><td>0</td><td>−4</td><td>0</td><td>−44/9</td><td>0</td></tr><tr><td><bold>t</bold><sup>6</sup></td><td>−4</td><td>4/3</td><td>2</td><td>1/3</td><td>1/3</td><td><bold>t</bold><sup>7</sup></td><td>−3</td><td>−8/3</td><td>−2</td><td>1/3</td><td>3</td><td><bold>t</bold><sup>8</sup></td><td>−1</td><td>4/3</td><td>−6</td><td>8/3</td><td>−4</td><td>28/9</td><td>−56/3</td></tr><tr><td><italic>I<sub>j</sub></italic></td><td>1</td><td>2</td><td>1</td><td>2</td><td>1</td><td><italic>I<sub>j</sub></italic></td><td>1</td><td>2</td><td>1</td><td>2</td><td>1</td><td><italic>I<sub>j</sub></italic></td><td>1</td><td>2</td><td>1</td><td>2</td><td>1</td><td>2</td><td>1</td></tr><tr><td /><td>2</td><td>3</td><td>3</td><td>4</td><td>4</td><td /><td>2</td><td>3</td><td>3</td><td>5</td><td>5</td><td /><td>2</td><td>3</td><td>3</td><td>5</td><td>5</td><td>6</td><td>6</td></tr><tr><td /><td>3</td><td>4</td><td>4</td><td>5</td><td>5</td><td /><td>3</td><td>6</td><td>6</td><td>6</td><td>6</td><td /><td>3</td><td>6</td><td>6</td><td>7</td><td>7</td><td>7</td><td>7</td></tr><tr><td /><td>5</td><td /><td /><td /><td /><td /><td>5</td><td /><td /><td /><td /><td /><td>5</td><td /><td /><td /><td /><td /><td /></tr></tbody></table> </ephtml> </p> <p>Table 1. Illustration of the Γ-algorithm, showing the generators a1, a2,..., a9 of the cone which dual cone is looked for, the dot products, the IA(u) sets, and the transformations associated with the different steps. Pivot columns are boldfaced.</p> <p> <ephtml> <table><thead valign="middle"><tr><td><bold>Phase 9</bold> (<italic>h</italic> = 9)</td><td><bold>Simplified dual</bold></td></tr><tr><td><bold>a</bold><sub>9</sub></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0084.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0085.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0086.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0087.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0088.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0089.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0090.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0091.gif" /></p></td><td><p><inline-graphic href="tmes_a_128561_o_ilm0092.gif" /></p></td><td /><td><bold>w</bold><sub>1</sub></td><td><bold>w</bold><sub>2</sub></td><td><bold>w</bold><sub>3</sub></td><td><bold>w</bold><sub>4</sub></td><td><bold>w</bold><sub>5</sub></td><td><bold>w</bold><sub>6</sub></td><td><bold>w</bold><sub>7</sub></td><td><bold>w</bold><sub>8</sub></td></tr></thead><tbody valign="bottom"><tr><td>2</td><td>0</td><td>0</td><td>−4</td><td>−8/3</td><td>4/3</td><td>0</td><td>8</td><td>−32/3</td><td>0</td><td /><td>0</td><td>0</td><td>0</td><td>−1</td><td>−2</td><td>−2</td><td>4</td><td>−1</td></tr><tr><td>2</td><td>−2</td><td>0</td><td>0</td><td>4</td><td>−8/3</td><td>−4</td><td>0</td><td>16/3</td><td>1232/27</td><td /><td>−2</td><td>1</td><td>0</td><td>0</td><td>3</td><td>1</td><td>0</td><td>0</td></tr><tr><td>4</td><td>1</td><td>−2</td><td>0</td><td>−8</td><td>8/3</td><td>4</td><td>16/3</td><td>16/3</td><td>0</td><td /><td>1</td><td>0</td><td>−1</td><td>0</td><td>−6</td><td>1</td><td>1</td><td>1</td></tr><tr><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>−4</td><td>−4</td><td>−24</td><td>−16</td><td>−2464/27</td><td /><td>0</td><td>−2</td><td>0</td><td>0</td><td>0</td><td>−3</td><td>−12</td><td>−2</td></tr><tr><td><bold>t</bold><sup>9</sup></td><td>0</td><td>−8</td><td>−8</td><td>−88/3</td><td>4</td><td>4</td><td>40/3</td><td>−16/3</td><td>0</td><td /><td /><td /><td /><td /><td /><td /><td /><td /></tr><tr><td><italic>I<sub>j</sub></italic></td><td>1</td><td>1</td><td>1</td><td>1</td><td>2</td><td>2</td><td>3</td><td>5</td><td>6</td><td><italic>I<sub>j</sub></italic></td><td>1</td><td>6</td><td>1</td><td>1</td><td>1</td><td>5</td><td>3</td><td>5</td></tr><tr><td /><td>2</td><td>3</td><td>5</td><td>6</td><td>3</td><td>5</td><td>6</td><td>7</td><td>7</td><td /><td>2</td><td>7</td><td>3</td><td>5</td><td>6</td><td>7</td><td>6</td><td>8</td></tr><tr><td /><td>3</td><td>6</td><td>7</td><td>7</td><td>8</td><td>8</td><td>8</td><td>8</td><td>8</td><td /><td>3</td><td>8</td><td>6</td><td>7</td><td>7</td><td>8</td><td>9</td><td>9</td></tr><tr><td /><td>5</td><td /><td /><td /><td /><td /><td /><td /><td>9</td><td /><td>5</td><td>9</td><td /><td /><td /><td /><td /><td /></tr><tr><td /><td>9</td><td /><td /><td /><td /><td /><td /><td /><td /><td /><td>9</td><td /><td /><td /><td /><td /><td /><td /></tr></tbody></table> </ephtml> </p> <p>From its last tableau (the one with the heading 'Simplified dual') we get that the dual of <bold>A</bold><subs>π</subs> in one of its minimal representations is</p> <p>Graph</p> <hd id="AN0023219924-27">4. Minimal representation of a cone. Edges of a cone and vertices of a polytope</hd> <p>The Γ-algorithm includes the test to append vectors to <bold>W</bold><sups>(<emph>h</emph>)</sups>, which is a powerful method to reduce the representation of the dual cone to a minimal representation. The following theorems show that the method is valid (see Castillo and Jubete [<reflink idref="bib17" id="ref22">17</reflink>]).</p> <hd id="AN0023219924-28">Theorem 1 (Dual after removing some generators of a cone)</hd> <p> <emph>Let</emph> <bold>A</bold> <subs>π</subs> =(<bold>a</bold><subs>1</subs>, ..., <bold>a</bold><subs><emph>s</emph></subs>)<subs>π</subs><emph>be a cone, and</emph><emph>its dual in minimal form, where</emph><bold>W</bold> = (<bold>w</bold><subs>1</subs>, ..., <bold>w</bold><subs><emph>p</emph></subs>).</p> <p> <emph>Let q</emph> ≤ <emph>p and</emph>, <emph>and denote A<subs>G</subs> the submatrix of</emph><bold>A</bold><emph>containing the columns on G. Then, we have</emph></p> <p>Graph</p> <p>The proof can be seen in Castillo and Jubete [<reflink idref="bib17" id="ref23">17</reflink>].</p> <hd id="AN0023219924-29">Theorem 2 (Identifying the edges of a cone)</hd> <p> <emph>Consider the cone</emph> <bold>A</bold> <subs>π</subs>, <emph>and let</emph>. <emph>If</emph></p> <p>Graph</p> <p> <emph>then</emph> <bold>A</bold> <subs>π</subs> =(<bold>A</bold>,∼<bold>a</bold><subs><emph>i</emph>1</subs>)<subs>π</subs>. <emph>In other words, we can remove the vector</emph><bold>a</bold><subs><emph>i</emph>1</subs><emph>from the set of generators</emph><bold>A</bold><emph>of</emph><bold>A</bold><subs>π</subs>, <emph>that is, it is not an edge of</emph><bold>A</bold><subs>π</subs>.</p> <p>For a proof, see Jubete [<reflink idref="bib20" id="ref24">20</reflink>].</p> <p>Once the edges have been identified, the minimal (in terms of edges) representation of the cone is obtained.</p> <hd id="AN0023219924-30">Example 2 (Edges and minimal representation of a cone)</hd> <p>To obtain the edges of the cone <bold>A</bold><subs>π</subs> in Example 1 we determine what are the redundant <bold>A</bold>-vectors. To this end, from the <emph>I<subs>j</subs></emph> set of the simplified dual in table 1, we obtain the sets</p> <p>Graph</p> <p>which are shown in table 2. Note that <emph>j</emph> ∈ <emph>I</emph><subs><emph>W</emph>(<bold>a</bold><emph>i</emph>)</subs> iff <emph>i</emph> ∈ <emph>I</emph><subs><emph>A</emph>(<bold>u</bold><emph>j</emph>)</subs>.</p> <p>Table 2. w vectors orthogonal to the initial set of generators showing the redundancy of vectors a2 and a4.</p> <p> <ephtml> <table><thead valign="middle"><tr><td /><td><bold>a</bold><sub>1</sub></td><td><bold>a</bold><sub>2</sub></td><td><bold>a</bold><sub>3</sub></td><td><bold>a</bold><sub>4</sub></td><td><bold>a</bold><sub>5</sub></td><td><bold>a</bold><sub>6</sub></td><td><bold>a</bold><sub>7</sub></td><td><bold>a</bold><sub>8</sub></td><td><bold>a</bold><sub>9</sub></td></tr></thead><tbody valign="top"><tr><td /><td>0</td><td>1</td><td>3</td><td>1</td><td>0</td><td>3</td><td>0</td><td>1</td><td>2</td></tr><tr><td /><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>2</td><td>2</td><td>2</td><td>2</td></tr><tr><td /><td>0</td><td>2</td><td>0</td><td>1</td><td>2</td><td>0</td><td>1</td><td>3</td><td>4</td></tr><tr><td /><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr><tr><td><italic>I<sub>j</sub></italic></td><td>1</td><td>1</td><td>1</td><td /><td>1</td><td>2</td><td>2</td><td>2</td><td>1</td></tr><tr><td /><td>3</td><td /><td>3</td><td /><td>4</td><td>3</td><td>4</td><td>6</td><td>2</td></tr><tr><td /><td>4</td><td /><td>7</td><td /><td>6</td><td>5</td><td>5</td><td>8</td><td>7</td></tr><tr><td /><td>5</td><td /><td /><td /><td>8</td><td>7</td><td>6</td><td /><td> 8</td></tr></tbody></table> </ephtml> </p> <p>Since <emph>I</emph><subs><emph>W</emph>(<bold>a</bold>2)</subs> ⊆ <emph>I</emph><subs><emph>W</emph>(<bold>a</bold>1)</subs>, <emph>I</emph><subs><emph>W</emph>(<bold>a</bold>4)</subs> ⊆ <emph>I</emph><subs><emph>W</emph>(<bold>a</bold>1)</subs>, and no other <emph>I</emph><subs><emph>W</emph>(<bold>a</bold><emph>r</emph>)</subs> is contained in another <emph>I</emph><subs><emph>W</emph>(<bold>a</bold><emph>s</emph>)</subs> for any <emph>s</emph>, the vectors <bold>a</bold><subs>2</subs> and <bold>a</bold><subs>4</subs> are redundant, i.e., they are not edges of the cone <bold>A</bold><subs>π</subs>. Thus, the edges are <bold>a</bold><subs>1</subs>,<bold>a</bold><subs>3</subs>,<bold>a</bold><subs>5</subs>,<bold>a</bold><subs>6</subs>,<bold>a</bold><subs>7</subs>,<subs>a</subs><subs>8</subs> and <bold>a</bold><subs>9</subs>.</p> <p>Thus, the minimal representation of the cone <bold>A</bold><subs>π</subs> in (<reflink idref="bib3" id="ref25">3</reflink>) is</p> <p>Graph</p> <hd id="AN0023219924-31">5. Facets of any dimension of cones and polytopes</hd> <p>Since (<emph>A</emph>(<bold>w</bold><subs><emph>j</emph></subs>))<subs>π</subs> is the main face associated with <bold>w</bold><subs><emph>j</emph></subs>, Theorem 1 allows one to obtain its dual and then its main faces, whose dimension is one unit less than that of (<emph>A</emph>(<emph>w<subs>j</subs></emph>))<subs>π</subs>. Consequently, once the dual of a cone has been obtained, a recursion allows one to obtain the duals of the cones associated with all facets of any dimension, and thus, the facets of lower dimensions.</p> <p>So, we can use Theorem 1 to determine the main facets of in a continuous process that identifies all elements of <bold>A</bold><subs>π</subs>.</p> <p>Graph</p> <p>where the symbol ∼ is used to refer to removed vectors.</p> <hd id="AN0023219924-32">Example 3 (Main facets of a cone)</hd> <p>The facets of dimension 2 of the cone in Example 1 can be obtained from the <emph>I<subs>j</subs></emph> set in the "simplified dual" tableau in table 1, after removing the index 2 (associated with the redundant vector <bold>a</bold><subs>2</subs>):</p> <p>Graph</p> <p>The facets of dimension <emph>k</emph> − 1 of a cone or a polytope are the intersections of its facets of dimension <emph>k</emph> not contained in other facets of dimension <emph>k</emph> − 1. Thus, once we know the facets of dimension <emph>k</emph>, we can use the following algorithm to obtain the facets of any dimension <emph>m</emph> < <emph>k</emph>.</p> <hd1 id="AN0023219924-33">Algorithm 2 (Facets of any dimension of a cone).</hd1> <p></p> <ulist> <item> <bold> • _B_Input:</bold> The set of generators {<bold>a</bold><subs>1</subs>,<bold>a</bold><subs>2</subs>, ..., <bold>a</bold><subs>s</subs>} of a cone, the set of its main facets {<emph>f</emph><subs>1</subs>,<emph>f</emph><subs>2</subs>, ... ,<emph>f<subs>r</subs></emph>}, and the corresponding dimension <emph>k</emph>.</item> <p></p> <item> <bold> • _B_Output:</bold> All the facets of the cone of any dimension <emph>m</emph> < <emph>k</emph>.</item> </ulist> <hd id="AN0023219924-34">Step 1:</hd> <p>If <emph>k</emph> = 1 then stop. Otherwise, let <emph>F</emph> = ∅.</p> <hd id="AN0023219924-35">Step 2:</hd> <p>For <emph>j</emph> = 1 to <emph>r</emph> and <emph>i</emph> = 1 to <emph>j</emph> − 1 append <emph>h</emph><subs>ℓ</subs> =<emph>f<subs>i</subs></emph>∩<emph>f<subs>j</subs></emph> to <emph>F</emph>.</p> <hd id="AN0023219924-36">Step 3:</hd> <p>Let <emph>m</emph> be the cardinal of <emph>F</emph>.</p> <hd id="AN0023219924-37">Step 4:</hd> <p>For <emph>i</emph> = <emph>m</emph> to 1 step −1 and <emph>j</emph> = <emph>m</emph> to 1 step −1 and <emph>j</emph> ≠ <emph>i</emph> remove <emph>h<subs>i</subs></emph> from <emph>F</emph> if <emph>h<subs>i</subs></emph> ⊆ <emph>h<subs>j</subs></emph>.</p> <hd id="AN0023219924-38">Step 5:</hd> <p>Output the set <emph>F</emph> as the set of facets of dimension <emph>k</emph>.</p> <hd id="AN0023219924-39">Step 6:</hd> <p>Let <emph>k</emph> = <emph>k</emph>−1 and go to Step 1.</p> <hd id="AN0023219924-40">Remark 1</hd> <p>The initial set of candidates to facets in Step 2 can be reduced if one takes into account that some intersections of <emph>f<subs>i</subs></emph> and <emph>f<subs>j</subs></emph> lead to empty sets, but this requires storing some extra information and controlling the set of indices to be used in the intersections. So, it is not clear whether or not it is worthwhile using this more complex methodology.</p> <hd id="AN0023219924-41">Theorem 3 (Characterization of the main facets of a polytype)</hd> <p> <emph>Let</emph> <bold>A</bold> <subs>λ</subs> <emph>be a polytope</emph>, <emph>and let</emph><emph>be its associated cone. The main facets of the polytope</emph><bold>A</bold><subs>λ</subs><emph>are the polytopes intersections of the main facets of its associated cone with the hyperplane x</emph><subs><emph>n</emph>+1</subs>=1.</p> <hd id="AN0023219924-42">Remark 2</hd> <p>From a dimensional point of view, if <emph>Q</emph>(<bold>w</bold><subs><emph>i</emph></subs>)≡{<bold>q</bold><subs>1</subs>,<bold>q</bold><subs>2</subs>, ..., <emph>q</emph><subs><emph>r</emph></subs>}, <sups><emph>L</emph></sups><bold>Q</bold> ≡ {<bold>q</bold><subs>1</subs>−<bold>q</bold><subs><emph>r</emph></subs>,<bold>q</bold><subs>2</subs>−<bold>q</bold><subs><emph>r</emph></subs>, ..., <bold>q</bold><subs><emph>r</emph>−1</subs>−<bold>q</bold><subs><emph>r</emph></subs>}, and we have , because the last component of <bold>a</bold><subs><emph>i</emph></subs>−<bold>a</bold><subs><emph>r</emph></subs> is null.</p> <p>In addition, <emph>a<subs>r</subs></emph> ∉ <sups><emph>L</emph></sups><bold>A</bold><subs>ρ</subs>, we have</p> <p>Graph</p> <p>This proves that the dimension of the main facets of the polytope <bold>A</bold><subs>λ</subs> is one unit less than the dimension of the main facets of the cone .</p> <hd id="AN0023219924-43">Example 4 (Facets of a polytope)</hd> <p>For the polytope associated with the cone in Example 1 we get (see Example 3):</p> <p>The facets of dimension 1, i.e., its edges, can be obtained using Algorithm 2, i.e. by intersections of the previous facets and removing subsets of others:</p> <p>Graph</p> <p>The facets of dimension 0 (vertices) can be obtained in the same form, to obtain:</p> <p>Graph</p> <p>The vertices and edges of this polytope are shown in figure 1.</p> <p>Graph: Figure 1. Polytope showing its vertices and edges.</p> <hd id="AN0023219924-44">6. Characterizing interior and boundary vectors in a cone</hd> <p>In this section we give some methods to determine whether or not a vector of a cone is interior to it or belongs to its boundary.</p> <p>Since the main facets of a cone contain all the boundary vectors in the cone, we have</p> <p>Graph</p> <p>To derive a method for identifying the interior and the boundary vectors of a cone we need the following theorem.</p> <hd id="AN0023219924-45">Theorem 4</hd> <p> <emph>Given a linear space</emph> <bold>A</bold> <subs>ρ</subs> <emph>and a vector</emph> <bold>x</bold> ∈ <bold>A</bold><subs>σ</subs>, <emph>then</emph></p> <p>Graph</p> <p>This theorem shows that a linear space of dimension <emph>s</emph> can be written as a cone with <emph>s</emph> + 1 generators. The proof can be seen in Castillo, Cobo, Jubete and Pruneda [<reflink idref="bib16" id="ref26">16</reflink>].</p> <hd id="AN0023219924-46">Theorem 5 (Characterization of the interior vectors in a cone)</hd> <p> <emph>A vector</emph> <bold>a</bold> ∈ <bold>A</bold><subs>π</subs><emph>belongs to the interior</emph><emph>of a cone</emph><bold>A</bold><subs>π</subs>, <emph>with dual</emph>, <emph>iff</emph></p> <p>Graph</p> <p>The proof can be seen in [<reflink idref="bib16" id="ref27">16</reflink>].</p> <hd id="AN0023219924-47">Corollary 1</hd> <p> <emph>A vector</emph> <bold>A</bold> <emph>belongs to the interior</emph> <emph>of a cone</emph> <bold>A</bold> <subs>π</subs>, <emph>with dual</emph>, <emph>iff</emph></p> <p>Graph</p> <p>The proof is obvious from Theorem 5 and taking into account that, since , we have <bold>a</bold><sups><emph>T</emph></sups><bold>W</bold> ≤ <bold>0</bold>.</p> <hd id="AN0023219924-48">Theorem 6 (Characterization of the boundary of a cone)</hd> <p> <emph>A vector</emph> <bold>A</bold> <emph>belongs to the boundary</emph> <emph>of a cone</emph> <bold>A</bold> <subs>π</subs> <emph>iff</emph> </p> <p>The proof is an immediate consequence of its definition and Theorem 5.</p> <hd id="AN0023219924-49">Example 5 (Interior and boundary in cones and polytopes)</hd> <p>The vector <bold>a</bold> = (<reflink idref="bib1" id="ref28">1</reflink>,<reflink idref="bib4" id="ref29">4</reflink>,<reflink idref="bib4" id="ref30">4</reflink>,<reflink idref="bib2" id="ref31">2</reflink>) is a boundary vector of the cone in Example 1, because , i.e., .</p> <p>The vector <bold>a</bold> = (<reflink idref="bib9" id="ref32">9</reflink>,<reflink idref="bib9" id="ref33">9</reflink>,<reflink idref="bib10" id="ref34">10</reflink>,<reflink idref="bib7" id="ref35">7</reflink>) is interior to the same cone, because</p> <p>Graph</p> <hd id="AN0023219924-50">7. Hypervolume of a polytope</hd> <p>In this section we derive a formula for calculating the hypervolume of a polytope. To this end, we note that if . We assume that we have already calculated</p> <p>Graph</p> <p>where the vectors in <bold>V</bold> ≡ {<bold>v</bold><subs>1</subs>, ..., <bold>v</bold><subs>f</subs>} are linearly independent, and then, dim<bold>V</bold><subs>ρ</subs> = <emph>f</emph>. In addition, , that is, <bold>V</bold><subs>ρ</subs> is the orthogonal complement in of the proper space of , i.e. of . So, we have</p> <p>Graph</p> <p>and taking into account (<reflink idref="bib7" id="ref36">7</reflink>)</p> <p>Graph</p> <p>The volume of <bold>Q</bold><subs>λ</subs>, denoted as <emph>V</emph>(<bold>Q</bold><subs>λ</subs>), is the sum of the volumes of the (<emph>n−f</emph>)-dimensional piramides with vertex any <bold>q</bold><subs><emph>r</emph></subs> ∈ <bold>Q</bold> and bases , given by the recursive expression</p> <p>Graph</p> <p>where <emph>I</emph> is the set of the main facets of <bold>Q</bold><subs>λ</subs>, and <bold>m</bold><subs><emph>i</emph></subs> is given by</p> <p>Graph</p> <p>with ν<subs><emph>i</emph></subs> and <emph>w</emph><subs><emph>i</emph></subs> the matrices that result after eliminating from <bold>V</bold> and <bold>w</bold><subs><emph>i</emph></subs> their last row and the last component, respectively. This is correct because:</p> <p></p> <ulist> <item> <bold> 1. because , and then , or in the form , and since , i.e., _B_m</bold> <subs> <emph>i</emph> </subs> belongs to the proper space of <bold>Q</bold><subs>λ</subs>.</item> <p></p> <item> <bold> 2. If _I_A_i_(_B_w</bold> <subs> <emph>i</emph> </subs>)=(<bold>a</bold><subs><emph>i</emph>1</subs>, ..., <bold>a</bold><subs><emph>ih</emph></subs>) we have and and then . Consequently, <bold>m</bold><subs><emph>i</emph></subs> is orthogonal to the facet .</item> <p></p> <item> <bold> 3. , and then _B_m</bold> <subs> <emph>i</emph> </subs> is an exterior normal.</item> </ulist> <p>Finally, we already know how to obtain</p> <p>Graph</p> <p>that is, the main facets of <bold>A</bold><subs>π</subs> that are also cones, and the main facets of <bold>Q</bold><subs>λ</subs>, and the process continues recursively.</p> <p>This justifies and suggests the following algorithm.</p> <hd1 id="AN0023219924-51">Algorithm 3 (Hypervolume of a polytope)</hd1> <p></p> <ulist> <item> <bold> • _B_Input:</bold> The set of vertices of a polytope <bold>Q</bold><subs>λ</subs>, the set of generators , with its last components removed, of the dual cone to its associated cone, and the set of its main facets</item> <p></p> </ulist> <p>• </p> <p>Graph</p> <p></p> <ulist> <item> In addition, for the recursion we need two sets <emph>V</emph>, <emph>T</emph> and <emph>S</emph>, initially empty.</item> <p></p> <item> <bold> • _B_Output:</bold> The hypervolume of the polytope <bold>Q</bold><subs>λ</subs>.</item> </ulist> <hd id="AN0023219924-52">Step 1:</hd> <p>If <emph>m</emph> = 2, i.e. if the polytope <bold>Q</bold><subs>λ</subs> has two vertices, <bold>q</bold><subs>1</subs> and <bold>q</bold><subs>2</subs>, then calculate the volume:</p> <p>Graph</p> <p>and return Vol.</p> <hd id="AN0023219924-53">Step 2:</hd> <p>Obtain the vertex <bold>q</bold><subs><emph>r</emph></subs> of the polytope <bold>Q</bold><subs>λ</subs> contained in the largest number of its main facets.</p> <hd id="AN0023219924-54">Step 3:</hd> <p>Let <emph>I</emph> be the set</p> <p>Graph</p> <p>In other words, obtain the set <emph>I</emph> of main facets of <bold>Q</bold><subs>λ</subs> not containing the vertex <bold>q</bold><subs><emph>r</emph></subs>.</p> <hd id="AN0023219924-55">Step 4:</hd> <p>Let Vol = 0 and <emph>i</emph> = 1.</p> <hd id="AN0023219924-56">Step 5:</hd> <p>Select the main facet of <bold>Q</bold><subs>λ</subs>, append <bold>w</bold><subs><emph>ji</emph></subs> to <emph>V</emph>, and choose one of its vertices, for example, the first <bold>q</bold><subs><emph>r</emph></subs>∈<emph>I</emph><emph>Q</emph>(<bold>w</bold><subs><emph>ji</emph></subs>). Store <bold>T</bold><subs><emph>i</emph></subs> = <bold>q</bold><subs><emph>i</emph>1</subs>−<bold>q</bold><subs><emph>r</emph></subs> in <emph>T</emph>.</p> <hd id="AN0023219924-57">Step 6:</hd> <p>Update <bold>Q</bold> using the formula</p> <p>Graph</p> <hd id="AN0023219924-58">Step 7:</hd> <p>Update the set of facets <emph>F</emph> (of the new <bold>Q</bold><subs>λ</subs>):</p> <p>Graph</p> <hd id="AN0023219924-59">Step 8:</hd> <p>Simplify the set <emph>F</emph> by removing any set contained in others in <emph>F</emph>.</p> <hd id="AN0023219924-60">Step 9:</hd> <p>Update the set <bold>w</bold> as</p> <p>Graph</p> <hd id="AN0023219924-61">Step 10:</hd> <p>Calculate the unit normal versor <bold>m</bold><subs><emph>i</emph></subs> orthogonal to the vectors in <emph>V</emph>, and store it in <emph>S</emph>.</p> <hd id="AN0023219924-62">Step 11:</hd> <p>Sum to Vol the volume of the new polytope <bold>Q</bold><subs>λ</subs> calling recursively to this algorithm with the new <bold>Q</bold>,<bold>W</bold>,<bold>F</bold>,<emph>V</emph> and <emph>S</emph>, i.e.</p> <p>Graph</p> <hd id="AN0023219924-63">Step 12:</hd> <p>If <emph>i</emph> = |<emph>I</emph>| then return Vol and exit. Otherwise, let <emph>i</emph> = <emph>i</emph>+1, and go to Step 5.</p> <hd id="AN0023219924-64">Example 6 (Volume of a polytope)</hd> <p>To calculate the volume of the polytope in Example 1 (figure 1) we use the Algorithm 3, as follows:</p> <p>Initially we have:</p> <p>Graph</p> <p>Graph</p> <hd id="AN0023219924-65">Step 1:</hd> <p>Since <emph>m</emph> > 2, we go to Step 2.</p> <hd id="AN0023219924-66">Step 2:</hd> <p>We select the vertex <bold>q</bold><subs><emph>r</emph></subs> = <bold>q</bold><subs>1</subs> because it is the one contained in the largest number of main facets.</p> <hd id="AN0023219924-67">Step 3:</hd> <p>The set <emph>I</emph> is the set</p> <p>Graph</p> <hd id="AN0023219924-68">Step 4:</hd> <p>We set Vol = 0 and <emph>i</emph> = 1.</p> <hd id="AN0023219924-69">Step 5:</hd> <p>We select the main facet {6,7,8,9}, append its associated vector <bold>w</bold><subs>2</subs> to <bold>V</bold>, choose the first vertex <bold>q</bold><subs>6</subs>, of this facet, and store <bold>q</bold><subs>2</subs>−<bold>q</bold><subs>6</subs> = (<reflink idref="bib3" id="ref37">3</reflink>,<reflink idref="bib2" id="ref38">2</reflink>,0) in <emph>T</emph>.</p> <hd id="AN0023219924-70">Step 6:</hd> <p>We update <bold>Q</bold> and get</p> <p>Graph</p> <hd id="AN0023219924-71">Step 7:</hd> <p>We update the set of facets <emph>F</emph>:</p> <p>Graph</p> <hd id="AN0023219924-72">Step 8:</hd> <p>Simplify the set <emph>F</emph> by removing any set contained in others in <emph>F</emph> and get</p> <p>Graph</p> <hd id="AN0023219924-73">Step 9:</hd> <p>Update the set <bold>w</bold> as</p> <p>Graph</p> <hd id="AN0023219924-74">Step 10:</hd> <p>We calculate the unit normal versor <bold>m</bold> = (0,1,0) (see table 4) orthogonal to the vectors in <emph>V</emph>, and store it in <emph>S</emph>.</p> <hd id="AN0023219924-75">Step 11:</hd> <p>Sum to Vol the volume of the new polytope <bold>Q</bold><subs>λ</subs> calling recursively to this algorithm with the new <bold>Q</bold>,<bold>W</bold>,<emph>F,V</emph> and <emph>S</emph>.</p> <p>Since we call again the algorithm, we start again with the new polytope <bold>Q</bold><subs>λ</subs>, but now the sets <emph>V</emph>, <emph>T</emph> and <emph>S</emph> are not empty. The process continues, as illustrated in table 3, where we can see that the desired volume is 53/6.</p> <p>Table 3. Illustration of the volume calculation process.</p> <p> <ephtml> <table><thead valign="middle"><tr><td>dim</td><td>polytope</td><td><italic>I</italic><sub><italic>Q</italic>(<bold>w</bold>j)</sub></td><td><bold>W</bold></td><td><bold>V</bold></td><td><bold>q</bold><sub><italic>i</italic>1</sub>−<bold>q</bold><sub><italic>r</italic></sub></td><td><bold>m</bold></td></tr></thead><tbody valign="top"><tr><td>4</td><td>1</td><td>{1, 3, 5, 9}</td><td>1</td><td /><td /><td /></tr><tr><td /><td>2</td><td>{6, 7, 8, 9}</td><td>2</td><td /><td /><td /></tr><tr><td /><td>3</td><td>{1, 3, 6}</td><td>3</td><td /><td /><td /></tr><tr><td /><td>4</td><td>{1, 5, 7}</td><td>4</td><td /><td /><td /></tr><tr><td /><td>5</td><td>{1, 6, 7}</td><td>5</td><td /><td /><td /></tr><tr><td /><td>6</td><td>{5, 7, 8}</td><td>6</td><td /><td /><td /></tr><tr><td /><td>7</td><td>{3, 6, 9}</td><td>7</td><td /><td /><td /></tr><tr><td /><td>8</td><td>{5, 8, 9}</td><td>8</td><td /><td /><td /></tr><tr><td /><td>9</td><td /><td /><td /><td /><td /></tr><tr><td>3</td><td>6</td><td>{6, 7}</td><td>5</td><td>2</td><td>{3, 2, 0}</td><td>{0, 1, 0}</td></tr><tr><td /><td>7</td><td>{7, 8}</td><td>6</td><td /><td /><td /></tr><tr><td /><td>8</td><td>{6, 9}</td><td>7</td><td /><td /><td /></tr><tr><td /><td>9</td><td>{8, 9}</td><td>8</td><td /><td /><td /></tr><tr><td>2</td><td>7</td><td>{7}</td><td>5</td><td>2</td><td>{3, 2, 0}</td><td>{0, 1, 0}</td></tr><tr><td /><td>8</td><td>{8}</td><td>8</td><td>6</td><td>{−3, 0, 1}</td><td>{−2, 0, 1}</td></tr><tr><td /><td /><td>volume = 7/3</td></tr><tr><td>2</td><td>8</td><td>{8}</td><td>6</td><td>2</td><td>{3, 2, 0}</td><td>{0, 1, 0}</td></tr><tr><td /><td>9</td><td>{9}</td><td>7</td><td>8</td><td>{−2, 0, 3}</td><td>{−1, 0, 1}</td></tr><tr><td /><td /><td>volume = 5/3</td></tr><tr><td /><td /><td>Total volume = 4</td></tr><tr><td>3</td><td>5</td><td>{7, 8}</td><td>2</td><td>6</td><td>{0, 1, 2}</td><td>{−2, 1, 1}</td></tr><tr><td /><td>7</td><td>{5, 7}</td><td>4</td><td /><td /><td /></tr><tr><td /><td>8</td><td>{5, 8}</td><td>8</td><td /><td /><td /></tr><tr><td>2</td><td>7</td><td>{7}</td><td>4</td><td>6</td><td>{0, 1, 2}</td><td>{−2, 1, 1}</td></tr><tr><td /><td>8</td><td>{8}</td><td>8</td><td>2</td><td>{0, 1, −1}</td><td><p><inline-graphic href="tmes_a_128561_o_ilm0129.gif" /></p></td></tr><tr><td /><td /><td>volume = 1/2</td><td /></tr><tr><td /><td /><td>Total volume = 1/2</td></tr><tr><td>3</td><td>3</td><td>{3, 9}</td><td>1</td><td>7</td><td>{3, 0, 0}</td><td>{4, 0, 1}</td></tr><tr><td /><td>6</td><td>{6, 9}</td><td>2</td><td /><td /><td /></tr><tr><td /><td>9</td><td>{3, 6}</td><td>3</td><td /><td /><td /></tr><tr><td>2</td><td>6</td><td>{9}</td><td>1</td><td>7</td><td>{3, 0, 0}</td><td>{4, 0, 1}</td></tr><tr><td /><td>9</td><td>{6}</td><td>3</td><td>2</td><td>{0, 2, 0}</td><td>{0, 1, 0}</td></tr><tr><td /><td /><td>volume = 4</td></tr><tr><td /><td /><td>Total volume = 4</td></tr><tr><td>3</td><td>5</td><td>{5, 9}</td><td>1</td><td>8</td><td>{0, 1, 2}</td><td>{−1, 0, 1}</td></tr><tr><td /><td>8</td><td>{8, 9}</td><td>2</td><td /><td /><td /></tr><tr><td /><td>9</td><td>{5, 8}</td><td>6</td><td /><td /><td /></tr><tr><td>2</td><td>8</td><td>{9}</td><td>1</td><td>8</td><td>{0, 1, 2}</td><td>{−1, 0, 1}</td></tr><tr><td /><td>9</td><td>{8}</td><td>6</td><td>2</td><td>{1, 1, 1}</td><td>{0, 1, 0}</td></tr><tr><td /><td /><td>volume = 1/3</td></tr><tr><td /><td /><td>Total volume = 1/3</td></tr><tr><td /><td /><td>Total volume = 53/6</td></tr></tbody></table> </ephtml> </p> <p>Note that in this process we have calculated the volumes of the polytopes {<bold>q</bold><subs>6</subs>,<bold>q</bold><subs>7</subs>,<bold>q</bold><subs>8</subs>}, {<bold>q</bold><subs>6</subs>,<bold>q</bold><subs>8</subs>,<bold>q</bold><subs>9</subs>}, {<bold>q</bold><subs>1</subs>,<bold>q</bold><subs>6</subs>,<bold>q</bold><subs>7</subs>,<bold>q</bold><subs>8</subs>,<bold>q</bold><subs>9</subs>}, {<bold>q</bold><subs>1</subs>,<bold>q</bold><subs>5</subs>,<bold>q</bold><subs>7</subs>,<bold>q</bold><subs>8</subs>}, {<bold>q</bold><subs>1</subs>,<bold>q</bold><subs>3</subs>,<bold>q</bold><subs>6</subs>,<bold>q</bold><subs>9</subs>}, and {<bold>q</bold><subs>1</subs>,<bold>q</bold><subs>5</subs>, <bold>q</bold><subs>8</subs>,<bold>q</bold><subs>9</subs>}, which are 7/3,5/3,4,1/2,4 and 1/3, respectively.</p> <p>Table 4 illustrates how the unit normals, which must be orthogonal to the vectors in <emph>V</emph>, are obtained using the methods described in Castillo, Cobo, Jubete and Pruneda [<reflink idref="bib16" id="ref39">16</reflink>], [<reflink idref="bib17" id="ref40">17</reflink>]. Note that these normals have been included in table 3.</p> <p>Table 4. Illustration of how the normals are obtained.</p> <p> <ephtml> <table><thead valign="middle"><tr><td>Volume 1</td><td>Volume 2</td><td>Volume 3</td><td>Volume 4</td></tr><tr><td><bold>w</bold><sub>2</sub></td><td><bold>w</bold><sub>2</sub></td><td><bold>w</bold><sub>6</sub></td><td><bold>w</bold><sub>8</sub></td><td><bold>m</bold><sub>11</sub></td><td><bold>m</bold><sub>12</sub></td><td><bold>w</bold><sub>6</sub></td><td><bold>w</bold><sub>6</sub></td><td><bold>w</bold><sub>2</sub></td><td><bold>m</bold><sub>2</sub></td><td><bold>w</bold><sub>7</sub></td><td><bold>w</bold><sub>7</sub></td><td><bold>w</bold><sub>2</sub></td><td><bold>m</bold><sub>3</sub></td><td><bold>w</bold><sub>8</sub></td><td><bold>w</bold><sub>8</sub></td><td><bold>w</bold><sub>2</sub></td><td><bold>m</bold><sub>4</sub></td></tr></thead><tbody valign="top"><tr><td>0</td><td>0</td><td>−2</td><td>−1</td><td>−2</td><td>−1</td><td>−2</td><td>−2</td><td>0</td><td>1/3</td><td>4</td><td>4</td><td>0</td><td>0</td><td>−1</td><td>−1</td><td>0</td><td>0</td></tr><tr><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>5/6</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td></tr><tr><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>−1/6</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td></tr><tr><td><bold>t</bold></td><td>1</td><td>1</td><td>0</td><td /><td /><td><bold>t</bold></td><td>6</td><td>1</td><td /><td><bold>t</bold></td><td>7</td><td>0</td><td /><td><bold>t</bold></td><td>2</td><td>0</td><td /></tr></tbody></table> </ephtml> </p> <hd id="AN0023219924-76">8. Conclusions</hd> <p>The Γ-algorithm has been shown to be an efficient algorithm for identifying all the main elements of a cone and a polytope, as its vertices, edges and facets of any dimension, together with the hypervolumes of these elements in the case of polytopes. The use of dual cones and the cone associated with a polytope become the key tools for solving these problems.</p> <hd id="AN0023219924-77">Acknowledgments</hd> <p>We thank Iberdrola, the Leonardo Torres Quevedo Foundation of the University of Cantabria and Dirección General de Investigación Científica y Técnica (DGICYT) (Project DPI2002-04172-C04-02), for partial support of this work. The authors also want to thank the Editor and one referee for their constructive and useful comments.</p> <ref id="AN0023219924-78"> <title> References </title> <blist> <bibl id="bib1" idref="ref1" type="bt">1</bibl> <bibtext> Minkowski, H. 1911. Gesammelte Abhandlugen, Berlin: Teubner.</bibtext> </blist> <blist> <bibl id="bib2" idref="ref2" type="bt">2</bibl> <bibtext> Motzkin, TS, Raiffa, H, Thompson, TS and Thrall, RM. 1966. "Double description method". In Contributions to the Theory of Games, Vol. 19, 51–73. Princeton, NJ: Princeton University Press.</bibtext> </blist> <blist> <bibl id="bib3" idref="ref3" type="bt">3</bibl> <bibtext> Chernikova, NV. 1965. An algorithm for finding a general formula for non-negative solutions of systems of linear inequalities. USSR Computational Mathematics and Mathematical Physics, 5: 228–233.</bibtext> </blist> <blist> <bibl id="bib4" idref="ref4" type="bt">4</bibl> <bibtext> Greenberg, H. 1975. An Algorithm for Determining Redundant Inequalities and all Solutions to Convex Polyhedra,. Numerische Mathematik, 24: 19–26.</bibtext> </blist> <blist> <bibl id="bib5" idref="ref5" type="bt">5</bibl> <bibtext> Dyer, ME. 1983. The complexity of vertex enumeration methods.. Mathematics of Operations Research, 8: 381–402.</bibtext> </blist> <blist> <bibl id="bib6" idref="ref6" type="bt">6</bibl> <bibtext> Fukuda, K and Prodon, A. 1996. "Double description method revisited". In Combinatorics and Computer Science Volume 1120 of Lecture Notes in Computer Science, Edited by: Deza, M, Euler, R and Manoussakis, I. 91–111. Springer-Verlag.</bibtext> </blist> <blist> <bibl id="bib7" idref="ref7" type="bt">7</bibl> <bibtext> Avis, D and Fukuda, K. 1992. A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete & Computational Geometry, 8: 295–313.</bibtext> </blist> <blist> <bibl id="bib8" idref="ref8" type="bt">8</bibl> <bibtext> Chazelle, B. 1993. An optimal convex hull algorithm in any fixed dimension. Discrete & Computational Geometry, 10: 377–409.</bibtext> </blist> <blist> <bibl id="bib9" idref="ref9" type="bt">9</bibl> <bibtext> Pillers Dobler, CE. 1994. A matrix approach to finding a set of generators and finding the polar (dual) of a class of polyhedral cones.. SIAM Journal on Matrix Analysis and Applications, 15: 796–803.</bibtext> </blist> <blist> <bibtext> Avis, D, Bremner, D and Seidel, R. 1997. How good are convex hull algorithms. Computational Geometry: Theory and Applications, 7: 265–302.</bibtext> </blist> <blist> <bibtext> Bremner, D, Fukuda, K and Marzetta, A. 1997. Primal-dual methods for vertex and facet enumeration. In Proc. 13th Annu. ACM Symposia in Computational Geometry, : 49–56.</bibtext> </blist> <blist> <bibtext> Fukuda, K, Liebling, TM and Margot, F. 1997. Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron.. Computational Geometry, 8: 1–12.</bibtext> </blist> <blist> <bibtext> Büeler, B, Enge, A and Fukuda, K. 2000. "Exact volume computation for convex polytopes: A practical study". In Polytopes – Combinatorics and Computation, DMV-Seminar 29, Edited by: Kalai, G and Ziegler, G. Birkhäuser Verlag.</bibtext> </blist> <blist> <bibtext> Laserre, JB. 1983. An analytical expression and an algorithm for the volume of a convex polyhedron in.. Journal of Optimization Theorey and Applications, 39: 363–377.</bibtext> </blist> <blist> <bibtext> Lawrence, J. 1991. Polytope volume computation. Mathematics of Computation, 57: 259–271.</bibtext> </blist> <blist> <bibtext> Castillo, E, Cobo, A, Jubete, F and Pruneda, RE. 1999. Orthogonal Sets and Polar Methods in Linear Algebra: Applications to Matrix Calculations, Systems of Equations and Inequalities, and Linear Programming, John Wiley and Sons.</bibtext> </blist> <blist> <bibtext> Castillo, E and Jubete, F. 2004. The Γ-algorithm and some applications.. International Journal of Mathematical Education in Science and Technology, 35: 369–389.</bibtext> </blist> <blist> <bibtext> Castillo, E, Jubete, F, Pruneda, RE and Solares, C. 2002. Obtaining simultaneous solutions of linear subsystems of equations and inequalities. Linear Algebra and its Applications, 346: 131–154.</bibtext> </blist> <blist> <bibtext> Jubete, F. 1991. El cono poliédrico convexo. Su incidencia en el álgebra lineal y la programación no lineal, Spain: CIS, Santander.</bibtext> </blist> <blist> <bibtext> Jubete, F. 1993. El Politopo. Su estructura geométrica y volumen exacto, Spain: CIS, Santander. Editorial</bibtext> </blist> <blist> <bibtext> Castillo, E, Cobo, A, Fernandez-Canteli, A, Jubete, F and Pruneda, RE. 1998. Updating Inverses in Matrix Analysis of Structures. International Journal for Numerical Methods in Engineering, 43: 1479–1504.</bibtext> </blist> <blist> <bibtext> Castillo, E, Cobo, A, Jubete, F, Pruneda, RE and Castillo, C. 2000. An orthogonally based pivoting transformation of matrices and some applications. SIAM Journal on Matrix Analysis, 22: 666–681.</bibtext> </blist> </ref> <aug> <p>By F. Jubete and E. Castillo</p> <p>Reported by Author; Author</p> </aug> <nolink nlid="nl1" bibid="bib10" firstref="ref10"></nolink> <nolink nlid="nl2" bibid="bib11" firstref="ref11"></nolink> <nolink nlid="nl3" bibid="bib12" firstref="ref12"></nolink> <nolink nlid="nl4" bibid="bib13" firstref="ref13"></nolink> <nolink nlid="nl5" bibid="bib14" firstref="ref14"></nolink> <nolink nlid="nl6" bibid="bib15" firstref="ref15"></nolink> <nolink nlid="nl7" bibid="bib21" firstref="ref16"></nolink> <nolink nlid="nl8" bibid="bib22" firstref="ref17"></nolink> <nolink nlid="nl9" bibid="bib16" firstref="ref18"></nolink> <nolink nlid="nl10" bibid="bib19" firstref="ref20"></nolink> <nolink nlid="nl11" bibid="bib17" firstref="ref21"></nolink> <nolink nlid="nl12" bibid="bib20" firstref="ref24"></nolink>
Header DbId: eric
DbLabel: ERIC
An: EJ753951
AccessLevel: 3
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: A Complete Description of Cones and Polytopes Including Hypervolumes of All Facets of a Polytope
– Name: Language
  Label: Language
  Group: Lang
  Data: English
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Jubete%2C+F%2E%22">Jubete, F.</searchLink><br /><searchLink fieldCode="AR" term="%22Castillo%2C+E%2E%22">Castillo, E.</searchLink>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="SO" term="%22International+Journal+of+Mathematical+Education+in+Science+%26+Technology%22"><i>International Journal of Mathematical Education in Science & Technology</i></searchLink>. Jan 2007 38(1):85-102.
– Name: Avail
  Label: Availability
  Group: Avail
  Data: Taylor & Francis, Ltd. 325 Chestnut Street Suite 800, Philadelphia, PA 19106. Tel: 800-354-1420; Fax: 215-625-2940; Web site: http://www.tandf.co.uk/journals/default.html
– Name: PeerReviewed
  Label: Peer Reviewed
  Group: SrcInfo
  Data: Y
– Name: Pages
  Label: Page Count
  Group: Src
  Data: 18
– Name: DatePubCY
  Label: Publication Date
  Group: Date
  Data: 2007
– Name: TypeDocument
  Label: Document Type
  Group: TypDoc
  Data: Journal Articles<br />Reports - Descriptive
– Name: Subject
  Label: Descriptors
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Algebra%22">Algebra</searchLink><br /><searchLink fieldCode="DE" term="%22Geometric+Concepts%22">Geometric Concepts</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+Formulas%22">Mathematical Formulas</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+Logic%22">Mathematical Logic</searchLink><br /><searchLink fieldCode="DE" term="%22Background%22">Background</searchLink><br /><searchLink fieldCode="DE" term="%22Illustrations%22">Illustrations</searchLink><br /><searchLink fieldCode="DE" term="%22Scientific+Methodology%22">Scientific Methodology</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematics+Education%22">Mathematics Education</searchLink>
– Name: ISSN
  Label: ISSN
  Group: ISSN
  Data: 0020-739X
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: In this paper methods and algorithms for identifying the main elements (edges and facets of any dimension) of a cone and a polytope, and calculating the corresponding hypervolumes are presented. The cones and polytopes are supposed to be given as the non-negative linear combination and the convex hull generated by a, not necessarily minimal, set of vectors (points), respectively, and they can be degenerated (of a dimension smaller than that of the proper space in which they are contained). First a minimum set of generators (edges and vertices) are obtained by eliminating the redundant vectors. In the case of cones, the linear space basis and the minimal cone generators are obtained. Second the set of all facets of any dimension are identified. Finally, an algorithm for obtaining the associated hypervolumes of any dimension, i.e. the length of its edges, the areas of its faces of dimension two, and the hypervolumes of its facets of any dimension, is introduced. The proposed formula leads to a recursion that gives the hypervolumes of dimension "n" as a function of other hypervolumes of dimension "n"-1. Examples are used to illustrate the proposed methods and algorithms. (Contains 4 tables and 1 figure.)
– Name: AbstractInfo
  Label: Abstractor
  Group: Ab
  Data: Author
– Name: Ref
  Label: Number of References
  Group: RefInfo
  Data: 22
– Name: DateEntry
  Label: Entry Date
  Group: Date
  Data: 2007
– Name: URL
  Label: Access URL
  Group: URL
  Data: <link linkTarget="URL" linkTerm="https://taylorandfrancis.metapress.com/link.asp?id=R4K5863536K1UK80" linkWindow="_blank">http://taylorandfrancis.metapress.com/link.asp?id=R4K5863536K1UK80</link>
– Name: AN
  Label: Accession Number
  Group: ID
  Data: EJ753951
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=eric&AN=EJ753951
RecordInfo BibRecord:
  BibEntity:
    Languages:
      – Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 18
        StartPage: 85
    Subjects:
      – SubjectFull: Algebra
        Type: general
      – SubjectFull: Geometric Concepts
        Type: general
      – SubjectFull: Mathematical Formulas
        Type: general
      – SubjectFull: Mathematical Logic
        Type: general
      – SubjectFull: Background
        Type: general
      – SubjectFull: Illustrations
        Type: general
      – SubjectFull: Scientific Methodology
        Type: general
      – SubjectFull: Mathematics Education
        Type: general
    Titles:
      – TitleFull: A Complete Description of Cones and Polytopes Including Hypervolumes of All Facets of a Polytope
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Jubete, F.
      – PersonEntity:
          Name:
            NameFull: Castillo, E.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 15
              M: 01
              Type: published
              Y: 2007
          Identifiers:
            – Type: issn-print
              Value: 0020-739X
          Numbering:
            – Type: volume
              Value: 38
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: International Journal of Mathematical Education in Science & Technology
              Type: main
ResultId 1