On the Universal Partition Theorem for 4-Polytopes

By means of sign-patterns any finite family of polynomials induces a decomposition of R ⁿ into basic semialgebraic sets. In case of integer coefficients the latter decomposition roughly appears to be a partition into realization spaces of 4 -polytopes. The latter is stated by the Universal Partition Theorem for 4 -polytopes by Richter-Gebert. The present paper presents a different proof. As its main tool, the von Staudt polytope is introduced. The von Staudt polytope constitutes the polytopal equivalent of the well-known von Staudt constructions for point configurations. With the aid of the von Staudt polytope the original ideas of universality theory can be directly applied to the polytopal case. Moreover, a new method for representing real values (on a computation line) by polytopal means is presented. This method implies a bundling strategy in order to duplicate the encoded information. Based on this approach, the following complexity result is obtained. The incidence code of a polytope, exhibiting a realization space equivalent to a given semialgebraic set, can be computed in the same time that it requires to generate the defining polynomial system. Received December 19, 1995, and in revised form December 16, 1996, April 28, 1997, and September 10, 1997.     

Cubical 4-Polytopes with Few Vertices

A cubical polytope is a convex polytope all of whose facets are conbinatorial cubes. A d-polytope Pis called almost simple if, in the graph of P, each vertex of Pis d-valent of (d+ 1)-valent. It is known that, for d> 4, all but one cubical d-polytopes with up to 2^d+1vertices are almost simple, which provides a complete enumeration of all the cubical d-polytopes with up to 2^d+1vertices. We show that this result is also true for d=4.     

一类非线性变分不等式解的稳定性

本文研究 Hilbert空间中一类强单调非线性变分不等式解的稳定性 ,所得结果表明强单调非线性变分不等式解的稳定性依赖于对应集合族与映射族的连续性 .     

Self-Dual Regular 4-Polytopes and Their Petrie-Coxeter-Polyhedra

Coxeter’s regular skew polyhedra in euclidean 4-space IE⁴ are intimately related to the self-dual regular 4-polytopes. The same holds for two of the three Petrie-Coxeter-polyhedra and the (self-dual) cubical tessellation in IE³. In this paper we discuss the combinatorial Petrie-Coxeter-polyhedra associated with the self-dual regular 4-incidence-polytopes.     

Shelling Polyhedral 3-Balls and 4-Polytopes

There is a long history of constructions of nonshellable triangulations of three-dimensional (topological) balls. This paper gives a survey of these constructions, including Furch's 1924 construction using knotted curves, which also appears in Bing's 1962 survey of combinatorial approaches to the Poincaré conjecture, Newman's 1926 explicit example, and M. E. Rudin's 1958 nonshellable triangulation of a tetrahedron with only 14 vertices (all on the boundary) and 41 facets. Here an (extremely simple) new example is presented: a nonshellable simplicial three-dimensional ball with only 10 vertices and 21 facets. It is further shown that shellings of simplicial 3 -balls and 4 -polytopes can ``get stuck': simplicial 4 -polytopes are not in general ``extendably shellable.' Our constructions imply that a Delaunay triangulation algorithm of Beichl and Sullivan, which proceeds along a shelling of a Delaunay triangulation, can get stuck in the three-dimensional version: for example, this may happen if the shelling follows a knotted curve. Received November 21, 1995, and in revised form September 20, 1996.     

关于凸函数的新不等式

考虑由Fejér不等式的右边部分生成的差值.通过建立积分恒等式,在导函数满足M-Lipschitz条件和导函数有界这两种情况下,给出这个差值的界的估计.     

凸正多胞体的自同构群的一个刻画

确定图和各种组合结构的自同构群历来是组合数学中重要且困难的问题.利用图的基本理论和置换群的一些初等结果对全体凸正多胞体的自同构群给出一个新的刻画.     

Cyclic Degrees of 3-Polytopes

 A precise upper bound is obtained for the minimum cyclic vertex degree in a 3-polytope with specified maximum face size. This implies improvements to some known upper bounds for the cyclic chromatic numbers of 3-polytopes. Received: August 18, 1997 Revised: August 24, 1998     

基于动力系统的线性不等式组的解法

本文提出了一种新的求解线性不等式组可行解的方法-基于动力系统的方法．假设线性不等式组的可行域为非空,在可行域的相对内域上建立一个非线性关系表达式,进而得到一个结构简单的动力系统模型．同时,定义了穿越方向。文章最后的数值实验结果表明此算法是有效的．     

一类新的求解非线性方程的七阶方法

利用权函数法给出了一类求解非线性方程单根的七阶收敛的方法.每步迭代需要计算三个函数值和一个导数值,因此方法的效率指数为1.627.数值试验给出了该方法与牛顿法及同类方法的比较,显示了该方法的优越性.最后指出Kou等人给出的七阶方法是方法的特例.     

求解线性不等式组的方法

本提出了一个新的求解线性不等式组可行解的方法－－无约束极值方法。通过在线性不等式组的非空可行域的相对内域上建立一个非线性极值问题，根据对偶关系，得到了一个对偶空间的无约束极值及原始，对偶变量之间的简单线性映射关系，这样将原来线性不等式组问题的求解转化为一个无约束极值问题。中主要讨论了求解无约束极值问题的共轭梯度算法。同时，在寻找不等式组可行解的过程中，定义了穿越方向，这样大大减少计算量。中最后数值实验结果表明此算法是有效的。     

关于几个新不等式

本文利用Redheffer不等式,Jordan不等式和Jensen不等式给出了一些新的不等式作为应用推广了文[1]的一个结果。     

Inequalities forf-vectors of 4-polytopes

LetV, E, S andF be the number of vertices, edges, subfacets and facets, respectively, of a 4-dimensional convex polytope. In this paper we derive new upper and lower bounds forS in terms ofF andV. Research supported by NSF grants GP-27963 and GP-19221.     

Approximation for Minimum Triangulations of Simplicial Convex 3-Polytopes

A minimum triangulation of a convex 3-polytope is a triangulation that contains the minimum number of tetrahedra over all its possible triangulations. Since finding minimum triangulations of convex 3-polytopes was recently shown to be NP-hard, it becomes significant to find algorithms that give good approximation. In this paper we give a new triangulation algorithm with an improved approximation ratio 2 - Ω(1/\sqrt n ) , where n is the number of vertices of the polytope. We further show that this is the best possible for algorithms that only consider the combinatorial structure of the polytopes. Received August 5, 2000, and in revised form March 29, 2001, and May 3, 2001. Online publication October 12, 2001.     

Heights of Minor Faces in 3-Polytopes

Siberian Mathematical Journal - Each 3-polytope has obviously a face  $ f $ of degree $ d(f) $ at most 5 which is called minor. The height $ h(f) $ of $ f $ is...     

Small Grid Embeddings of 3-Polytopes

We introduce an algorithm that embeds a given 3-connected planar graph as a convex 3-polytope with integer coordinates. The size of the coordinates is bounded by O(2^7.55n )=O(188 ⁿ ). If the graph contains a triangle we can bound the integer coordinates by O(2^4.82n ). If the graph contains a quadrilateral we can bound the integer coordinates by O(2^5.46n ). The crucial part of the algorithm is to find a convex plane embedding whose edges can be weighted such that the sum of the weighted edges, seen as vectors, cancel at every point. It is well known that this can be guaranteed for the interior vertices by applying a technique of Tutte. We show how to extend Tutte’s ideas to construct a plane embedding where the weighted vector sums cancel also on the vertices of the boundary face.     

Cautious Non-Linear Optimisation: A New Technique for Allocation Problems

Solutions of linear programming formulations of some problems may be unsatisfactory, because they inherently tend to be extreme, sparse, and ruthless. A method of non-linear optimisation is described which is cautious in the sense that a progressive restraint is imposed on departures from some reference solution. Constraints can be incorporated provided they are regarded as somewhat flexible. Multiple objectives may also be pursued. Large problems (more than 1000 variables) may be handled without difficulty by employing conjugate gradient methods of optimisation. Computing requirements are no greater than for an equivalent LP problem, and execution times to obtain satisfactory approximate solutions may be less.The method has been successfully applied to a large fishery management problem, which is described. It yields stable, realistic solutions, and enables a range of solutions corresponding to different assumptions about the importance of various processes to be generated with confidence.     

一个关于混合变分不等式问题的投影算法

作者提出了混合变分不等式的一个新的投影算法. 混合变分不等式在弹性塑料学领域有实际应用, 而且形式上比经典的变分不等式更一般. 假设映射具有某种伪单调性, 作者证明了所提出的新算法是全局收敛的. 如果某种误差届成立, 算法的收敛率也被分析.     

共轭A-调和张量新的双权积分不等式

共轭A-调和张量的一些局部A_r~(λ3)(λ_1,λ_2,Ω)-加权积分不等式得到了证明,它们可看作是共轭调和函数和p-调和函数相应结果的推广．这些结果可用来研究共轭调和函数的可积性并估计它们的积分．同时也给出上述结果在拟正则映射中的应用．     

关于二阶导数的若干新积分不等式

根据Cauchy-Schwarz不等式,得到了C2([a,b])空间中函数的二阶导数的若干新积分不等式.