Annotation of OpenXM_contrib/PHC/Ada/Root_Counts/Stalift/inner_normal_cones.ads, Revision 1.1.1.1
1.1 maekawa 1: with Standard_Integer_Vectors; use Standard_Integer_Vectors;
2: with Standard_Integer_Matrices; use Standard_Integer_Matrices;
3: with Lists_of_Integer_Vectors; use Lists_of_Integer_Vectors;
4: with Integer_Faces_of_Polytope; use Integer_Faces_of_Polytope;
5:
6: package Inner_Normal_Cones is
7:
8: -- DESCRIPTION :
9: -- This package contains facilities for dealing with inner normal cones,
10: -- that are cones normal to some faces of a given polytope, with apex
11: -- at the origin. Especially the normal cones to vertices are of great
12: -- interest to determine which points contribute to the mixed volume.
13: -- The primal representation of a normal cone consists in the generators
14: -- of the cone. A matrix of inequalities defines the dual representation.
15:
16: -- CONSTRUCTORS FOR PRIMAL REPRESENTATION :
17:
18: function Generators ( l : List; facets : Faces; x : Vector ) return List;
19:
20: -- DESCRIPTION :
21: -- Returns the generators of the polyhedral cone, which lies in the
22: -- dual space of the polytope spanned by l and is enclosed by the facets,
23: -- which all contain the vector x.
24: -- The list on return contains all inner normals to the facets.
25:
26: function Generators ( l : List; x : Vector ) return List;
27:
28: -- DESCRIPTION :
29: -- Returns the generators of the polyhedral cone to conv(l),
30: -- normal at the vector x.
31:
32: -- CONSTRUCTOR FOR DUAL REPRESENTATION :
33:
34: function Inner_Normal_Cone ( l : List; x : Vector ) return Matrix;
35:
36: -- DESCRIPTION :
37: -- Returns the inequalities that define the normal cone to the vector x,
38: -- normal to the polytope spanned by the points in l.
39: -- The range of the matrix on return is (x'range,1..Length_Of(l)-1),
40: -- which implies that the inequalities are stored columnwise.
41: -- The type of the inequalities is >= 0.
42:
43: function Included_Normal_Cone ( gx : List; x : Vector ) return Matrix;
44:
45: -- DESCRIPTION :
46: -- Returns the inequalities that define the inner normal cone to the
47: -- vector x, such that these normals are pointing in the interior of
48: -- the polytope spanned by l, when their basis is the point x.
49: -- The walls of this cone are the facets, the list gx should
50: -- contain all inner normal to the facets at the vertex x.
51:
52: -- RANGE FORMATS :
53: -- The matrix on return has ranges (x'first-1..x'last,1..Length_Of(gx)).
54: -- The first row of the matrix contains <gx,x>,
55: -- to be used in the right-hand side of the inequalities.
56:
57: -- PRIMITIVE SELECTORS :
58:
59: function Evaluate ( m : Matrix; i : integer; v : Vector ) return integer;
60:
61: -- DESCRIPTION :
62: -- Evaluates the vector in the ith hyperplane of the inequality matrix.
63:
64: function Satisfies ( m : Matrix; i : integer; v : Vector ) return boolean;
65: function Strictly_Satisfies ( m : Matrix; i : integer; v : Vector )
66: return boolean;
67:
68: -- DESCRIPTION :
69: -- Returns true if the vector v satisfies the ith inequality of the matrix.
70: -- With Strictly_ true is only returned if the evaluation yields a
71: -- positive result.
72:
73: function Satisfies ( m : Matrix; v : Vector ) return boolean;
74: function Strictly_Satisfies ( m : Matrix; v : Vector ) return boolean;
75:
76: -- DESCRIPTION :
77: -- Returns true if the vector v satisfies all inequalities defined by m.
78:
79: function Satisfies ( m : Matrix; v : List ) return boolean;
80: function Strictly_Satisfies ( m : Matrix; v : List ) return boolean;
81:
82: -- DESCRIPTION :
83: -- Returns true if all vectors in v satisfy all inequalities defined by m.
84:
85: -- SECONDARY SELECTORS :
86:
87: function Satisfy ( m : Matrix; l : List ) return List;
88: function Strictly_Satisfy ( m : Matrix; l : List ) return List;
89:
90: -- DESCRIPTION :
91: -- Returns a list of points from l that (strictly) satisfy the
92: -- inequalities in the matrix.
93:
94: function Contained_in_Cone ( l : List; x : Vector; v : List ) return boolean;
95: function Strictly_Contained_in_Cone ( l : List; x : Vector; v : List )
96: return boolean;
97:
98: -- DESCRIPTION :
99: -- Returns true when all vectors in v are contained in the normal cone
100: -- to the points in l, at the vector x.
101:
102: function Contained_in_Cone ( l,v : List ) return boolean;
103: function Strictly_Contained_in_Cone ( l,v : List ) return boolean;
104:
105: -- DESCRIPTION :
106: -- Returns true when there exists a normal cone to the points in l
107: -- that entirely contains the points in v.
108:
109: -- CONCERNING THE UNION OF CONES :
110:
111: function In_Union ( v1,v2 : Vector; k1,k2 : Matrix ) return boolean;
112:
113: -- DESCRIPTION :
114: -- Returns true if the convex combination of v1 and v2 is contained
115: -- in the union of the convex cones k1 and k2, given by their
116: -- inequality matrix.
117:
118: -- REQUIRED : Satisfies(k1,v1) and Satisfies(k2,v2).
119:
120: function In_Union ( v1,v2 : List; k1,k2 : Matrix ) return boolean;
121:
122: -- DESCRIPTION :
123: -- Returns true if every convex combination of a vector from v1
124: -- and a vector from v2 is contained in the union of the convex
125: -- cones k1 and k2, given by their inequality matrix.
126:
127: -- REQUIRED : Satisfies(k1,v1) and Satisfies(k2,v2).
128:
129: end Inner_Normal_Cones;
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>