mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, specifically

convex geometry In mathematics, convex geometry is the branch of geometry studying convex sets, mainly in Euclidean space. Convex sets occur naturally in many areas: computational geometry, convex analysis, discrete geometry, functional analysis, geometry of numbe ...

, the normal fan of a

convex polytope A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...

''P'' is a polyhedral fan that is

dual Dual or Duals may refer to: Paired/two things * Dual (mathematics), a notion of paired concepts that mirror one another ** Dual (category theory), a formalization of mathematical duality *** see more cases in :Duality theories * Dual (grammatical ...

to ''P''. Normal fans have applications to

polyhedral combinatorics Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes. Research in polyhedral comb ...

linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...

tropical geometry In mathematics, tropical geometry is the study of polynomials and their geometric properties when addition is replaced with minimization and multiplication is replaced with ordinary addition: : x \oplus y = \min\, : x \otimes y = x + y. So f ...

and other areas of mathematics.

Definition

Given a convex polytope ''P'' in R^''n'', the normal fan ''N''_''P'' of ''P'' is a polyhedral fan in the

dual space In mathematics, any vector space ''V'' has a corresponding dual vector space (or just dual space for short) consisting of all linear forms on ''V'', together with the vector space structure of pointwise addition and scalar multiplication by const ...

, (R^''n'')* whose

cones A cone is a three-dimensional geometric shape that tapers smoothly from a flat base (frequently, though not necessarily, circular) to a point called the apex or vertex. A cone is formed by a set of line segments, half-lines, or lines conn ...

consist of the normal cone ''C''_''F'' to each face ''F'' of ''P'', :

N_P = \_.

Each normal cone ''C''_''F'' is defined as the set of linear functionals ''w'' such that the set of points ''x'' in ''P'' that maximize ''w''(''x'') contains ''F'', :

C_F = \.

Properties

* ''N''_''P'' is a ''complete fan'', meaning the union of its cones is the whole space, (R^''n'')*. * If ''F'' is a face of ''P'' of dimension ''d'', then its normal cone ''C''_''F'' has dimension ''n'' – ''d''. The normal cones to vertices of ''P'' are full dimensional. If ''P'' has full dimension, the normal cones to the facets of ''P'' are the rays of ''N''_''P'' and the normal cone to ''P'' itself is ''C''_''P'' = , the zero cone. * The affine span of face ''F'' of ''P'' is

orthogonal In mathematics, orthogonality is the generalization of the geometric notion of ''perpendicularity''. By extension, orthogonality is also used to refer to the separation of specific features of a system. The term also has specialized meanings in ...

to the linear span of its normal cone, ''C''_''F''. * The correspondence between faces of ''P'' and cones of ''N''_''P'' reverses inclusion, meaning that for faces ''F'' and ''G'' of ''P'', ::

F \subseteq G \quad \Leftrightarrow \quad C_F \supseteq C_G.

* Since ''N''_''P'' is a fan, the

intersection In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their i ...

of any two of its cones is also a cone in ''N''_''P''. For faces ''F'' and ''G'' of ''P'', ::

C_F \cap C_G = C_H

:where ''H'' is the smallest face of ''P'' that contains both ''F'' and ''G''.

Applications

* If polytope ''P'' is thought of as the

feasible region In mathematical optimization, a feasible region, feasible set, search space, or solution space is the set of all possible points (sets of values of the choice variables) of an optimization problem that satisfy the problem's constraints, potent ...

of a

linear program Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...

, the normal fan of ''P'' partitions the space of objective functions based on the solution set to the linear program defined by each. The linear program in which the goal is to maximize linear objective function ''w'' has solution set ''F'' if and only if ''w'' is in the

relative interior In mathematics, the relative interior of a set is a refinement of the concept of the interior, which is often more useful when dealing with low-dimensional sets placed in higher-dimensional spaces. Formally, the relative interior of a set S (de ...

of the cone ''C''_''F''. * If polytope ''P'' has the

origin Origin(s) or The Origin may refer to: Arts, entertainment, and media Comics and manga * Origin (comics), ''Origin'' (comics), a Wolverine comic book mini-series published by Marvel Comics in 2002 * The Origin (Buffy comic), ''The Origin'' (Bu ...

in its

interior Interior may refer to: Arts and media * ''Interior'' (Degas) (also known as ''The Rape''), painting by Edgar Degas * ''Interior'' (play), 1895 play by Belgian playwright Maurice Maeterlinck * ''The Interior'' (novel), by Lisa See * Interior de ...

, then the normal fan of ''P'' can be constructed from the polar dual of ''P'' by taking the cone over each face of the dual polytope, ''P''°. * For ''f'' a polynomial in ''n'' variables with coefficients in C, the tropical hypersurface of ''f'' is supported on a subfan of the normal fan of the

Newton polytope In mathematics, the Newton polytope is an integral polytope associated with a multivariate polynomial. It can be used to analyze the polynomial's behavior when specific variables are considered negligible relative to the others. Specifically, give ...

''P'' of ''f''. In particular, the tropical hypersurface is supported on the cones in ''N''_''P'' of dimension less than ''n''.

References

*. {{refend Geometric objects