Poset extensions, convex sets, and semilattice presentations

The paper is devoted to an algebraic and geometric study of the feasible set of a poset, the set of finite probability distributions on the elements of the poset whose weights satisfy the order relationships specified by the poset. For a general poset, this feasible set is a barycentric algebra. The feasible sets of the order structures on a given finite set are precisely the convex unions of the primary simplices, the facets of the first barycentric subdivision of the simplex spanned by the elements of the set. As another fragment of a potential complete duality theory for barycentric algebras, a duality is established between order-preserving mappings and embeddings of feasible sets. In particular, the primary simplices constituting the feasible set of a given finite poset are the feasible sets of the linear extensions of the poset. A finite poset is connected if and only if its barycentre is an extreme point of its feasible set. The feasible set of a (general) disconnected poset is the join of the feasible sets of its components. The extreme points of the feasible set of a finite poset are specified in terms of the disjointly irreducible elements of the semilattice presented by the poset. Semilattices presented by posets are characterised in terms of various distributivity concepts.     

Largest integral simplices with one interior integral point: Solution of Hensley's conjecture and related results

For each dimension d, d-dimensional integral simplices with exactly one interior integral point have bounded volume. This was first shown by Hensley. Explicit volume bounds were determined by Hensley, Lagarias and Ziegler, Pikhurko, and Averkov. In this paper we determine the exact upper volume bound for such simplices and characterize the volume-maximizing simplices. We also determine the sharp upper bound on the coefficient of asymmetry of an integral polytope with a single interior integral point. This result confirms a conjecture of Hensley from 1983. Moreover, for an integral simplex with precisely one interior integral point, we give bounds on the volumes of its faces, the barycentric coordinates of the interior integral point and its number of integral points. Furthermore, we prove a bound on the lattice diameter of integral polytopes with a fixed number of interior integral points. The presented results have applications in toric geometry and in integer optimization.     

Barycentric coordinates for convex sets

In this paper we provide an extension of barycentric coordinates from simplices to arbitrary convex sets. Barycentric coordinates over convex 2D polygons have found numerous applications in various fields as they allow smooth interpolation of data located on vertices. However, no explicit formulation valid for arbitrary convex polytopes has been proposed to extend this interpolation in higher dimensions. Moreover, there has been no attempt to extend these functions into the continuous domain, where barycentric coordinates are related to Green’s functions and construct functions that satisfy a boundary value problem. First, we review the properties and construction of barycentric coordinates in the discrete domain for convex polytopes. Next, we show how these concepts extend into the continuous domain to yield barycentric coordinates for continuous functions. We then provide a proof that our functions satisfy all the desirable properties of barycentric coordinates in arbitrary dimensions. Finally, we provide an example of constructing such barycentric functions over regions bounded by parametric curves and show how they can be used to perform freeform deformations.      

More Characterizations of Certain Special Families of Simplices

This paper is about various characterizations of orthocentric, and other special types of, d-dimensional simplices and related issues. It puts together several three-dimensional results that are scattered in the literature, and establishes stronger versions and extensions to higher dimensions. These compactly organized results, which are mostly new for higher dimensions, are expected to be very useful tools for further research. Several open problems are posed.     

Barycentric coordinates for Lagrange interpolation over lattices on a simplex

In this paper, a (d?+?1)-pencil lattice on a simplex in ${\mathbb{R}}^d$ is studied. The lattice points are explicitly given in barycentric coordinates. This enables the construction and the efficient evaluation of the Lagrange interpolating polynomial over a lattice on a simplex. Also, the barycentric representation, based on shape parameters, turns out to be appropriate for the lattice extension from a simplex to a simplicial partition.     

On the evaluation of rational triangular Bézier surfaces and the optimal stability of the basis

An efficient evaluation algorithm for rational triangular Bernstein–Bézier surfaces with any number of barycentric coordinates is presented and analyzed. In the case of three barycentric coordinates, it coincides with the usual rational triangular de Casteljau algorithm. We perform its error analysis and prove the optimal stability of the basis. Comparisons with other evaluation algorithms are included, showing the better stability properties of the analyzed algorithm.     

Volume and Lattice Points of Reflexive Simplices

Using new number-theoretic bounds on the denominators of unit fractions summing up to one, we show that in any dimension d ≥ 4 there is only one d-dimensional reflexive simplex having maximal volume. Moreover, only these reflexive simplices can admit an edge that has the maximal number of lattice points possible for an edge of a reflexive simplex. In general, these simplices are also expected to contain the largest number of lattice points even among all lattice polytopes with only one interior lattice point. Translated in algebro-geometric language, our main theorem yields a sharp upper bound on the anticanonical degree of d-dimensional Q-factorial Gorenstein toric Fano varieties with Picard number one, e.g., of weighted projective spaces with Gorenstein singularities.     

关于单形的几个不等式及其应用

Using theory of distance geometry and analytic method, the problem on relations about the volumes of some simplices is studied, and some new inequalities for the volumes of simplices are established. As special cases, an inequality for the volume of the pedal simplex of a simplex and other inequalities for simplices are gotten.     

Copositivity Detection of Tensors: Theory and Algorithm

A symmetric tensor is called copositive if it generates a multivariate form taking nonnegative values over the nonnegative orthant. Copositive tensors have found important applications in polynomial optimization, tensor complementarity problems and vacuum stability of a general scalar potential. In this paper, we consider copositivity detection of tensors from both theoretical and computational points of view. After giving several necessary conditions for copositive tensors, we propose several new criteria for copositive tensors based on the representation of the multivariate form in barycentric coordinates with respect to the standard simplex and simplicial partitions. It is verified that, as the partition gets finer and finer, the concerned conditions eventually capture all strictly copositive tensors. Based on the obtained theoretical results with the help of simplicial partitions, we propose a numerical method to judge whether a tensor is copositive or not. The preliminary numerical results confirm our theoretical findings.     

一类涉及两个单形的三角不等式及其应用

应用解析方法和几何不等式理论研究了n维欧氏空间En中涉及两个n维单形的几何不等式问题,建立了涉及两个单形的一类三角不等式.作为其应用,获得了涉及两个单形及其内点的几何不等式,特别,获得了n维单形与其垂足单形的体积的一类关系式,改进了关于垂足单形体积的几类几何不等式.     

三角形的九点二次曲线

在任意三角形内,三边中点,三高的垂足,以及连接顶点与垂心的三线段的中点,都在同一圆上,此圆即为三角形九点圆.三角形的九点圆是欧氏几何中著名的优美定理,被称为欧拉圆和费尔巴哈圆.本文试图把垂心改换为平面内的任意点,相应地把三条高线改换为过每个顶点各一条的共点直线组时,则将把三角形的九点圆有趣地推广为三角形的九点二次曲线.并具体讨论在不同的区域内得到的九点二次曲线.     

Algorithmic copositivity detection by simplicial partition

We present new criteria for copositivity of a matrix, i.e., conditions which ensure that the quadratic form induced by the matrix is nonnegative over the nonnegative orthant. These criteria arise from the representation of the quadratic form in barycentric coordinates with respect to the standard simplex and simplicial partitions thereof. We show that, as the partition gets finer and finer, the conditions eventually capture all strictly copositive matrices. We propose an algorithmic implementation which considers several numerical aspects. As an application, we present results on the maximum clique problem. We also briefly discuss extensions of our approach to copositivity with respect to arbitrary polyhedral cones.     

Barycentric coordinates for convex polytopes

An extension of the standard barycentric coordinate functions for simplices to arbitrary convex polytopes is described. The key to this extension is the construction, for a given convex polytope, of a unique polynomial associated with that polytope. This polynomial, theadjoint of the polytope, generalizes a previous two-dimensional construction described by Wachspress. The barycentric coordinate functions for the polytope are rational combinations of adjoints of various dual cones associated with the polytope.     

Concurrency of the altitudes of a triangle

Of all the traditional (or Greek) centers of a triangle, the orthocenter (i.e., the point of concurrence of the altitudes) is probably the one that attracted the most of attention. This may be due to the fact that it is the only one that has no exact analogue for arbitrary higher dimensional simplices, for spherical and hyperbolic triangles, or for triangles in normed planes. But it possibly has to do also with the non-existence of any explicit treatment of this center in the Greek works that have come down to us. In this paper we present different proofs of the fact that the altitudes of a triangle are concurrent. These include the first extant proof, in the works of al-Kūhī, Newton’s proof, Gauss’s proof, and other interesting proofs.     

SPHERICAL SIMPLICES AND THEIR POLARS

This article is about spherical simplices in the unit sphere.One of the purposes is to give a relation of dihedral anglesof a spherical simplex and its polar, and the other is to givetwo simple formulae of volumes of spherical simplices and theirpolars. We can calculate the volume of a spherical simplex andthe sum of volumes of it and its polar from these formulae forthe unit sphere in the odd- and even-dimensional Euclidean spaces,respectively.     

伪对称点集与正则单形

要证明了E~n中的有序向量集是伪对称点集的充要条件.利用这一充分必要条件,得到了有关正则单形的几个等价描述,给出了伪对称点集与正则单形的关系的一个结论:设■={A_1,A_2,…,A_(n+1)}是E~n中的点集,则■是n维对称点集的充要条件是以(?)为顶点的单形是正则单形.     

Delaunay configurations and multivariate splines: A generalization of a result of B. N. Delaunay

In the 1920s, B. N. Delaunay proved that the dual graph of the Voronoi diagram of a discrete set of points in a Euclidean space gives rise to a collection of simplices, whose circumspheres contain no points from this set in their interior. Such Delaunay simplices tessellate the convex hull of these points. An equivalent formulation of this property is that the characteristic functions of the Delaunay simplices form a partition of unity. In the paper this result is generalized to the so-called Delaunay configurations. These are defined by considering all simplices for which the interiors of their circumspheres contain a fixed number of points from the given set, in contrast to the Delaunay simplices, whose circumspheres are empty. It is proved that every family of Delaunay configurations generates a partition of unity, formed by the so-called simplex splines. These are compactly supported piecewise polynomial functions which are multivariate analogs of the well-known univariate B-splines. It is also shown that the linear span of the simplex splines contains all algebraic polynomials of degree not exceeding the degree of the splines.

     

Retract-collapsible graphs and invariant subgraph properties

A (finite or infinite) graph G is retract-collapsible if it can be dismantled by deleting systematically at each step every vertex that is strictly dominated, in such a way that the remaining subgraph is a retract of G, and so as to get a simplex at the end. A graph is subretract-collapsible if some graph obtained by planting some rayless tree at each of its vertices is retract-collapsible. It is shown that the subretract-colapsible graphs are cop-win; and that a ball-Helly graph is subretract-collapsible if and only if it has no isometric infinite paths (thus in particular if it has no infinite paths, or if it is bounded). Several fixed subgraph properties are proved. In particular, if G is a subretract-collapsible graph, and f a contraction from G into G, then (i) if G has no infinite simplices, then f(S) = S for some simplex S of G; and (ii) if the dismantling of G can be achieved in a finite number of steps and if some family of simplices of G has a compacity property, then there is a simplex S of G such that f(S) ? S. This last result generalizes a property of bounded ball-Helly graphs. © 1995 John Wiley & Sons, Inc.     

The uses of homogeneous barycentric coordinates in plane Euclidean geometry

The notion of homogeneous barycentric coordinates provides a powerful tool for analysing problems in plane geometry. The paper explains the advantages over the traditional use of trilinear coordinates, and illustrates its power in leading to discoveries of new and interesting collinearity relations of points associated with a triangle.