Convex lattice polygons with all lattice points visible

Two lattice points are visible to one another if there exist no other lattice points on the line segment connecting them. In this paper we study convex lattice polygons that contain a lattice point such that all other lattice points in the polygon are visible from it. We completely classify such polygons, show that there are finitely many of lattice width greater than 2, and computationally enumerate them. As an application of this classification, we prove new obstructions to graphs arising as skeleta of tropical plane curves.     

Nonlinear rescaling and proximal-like methods in convex optimization

The nonlinear rescaling principle (NRP) consists of transforming the objective function and/or the constraints of a given constrained optimization problem into another problem which is equivalent to the original one in the sense that their optimal set of solutions coincides. A nonlinear transformation parameterized by a positive scalar parameter and based on a smooth sealing function is used to transform the constraints. The methods based on NRP consist of sequential unconstrained minimization of the classical Lagrangian for the equivalent problem, followed by an explicit formula updating the Lagrange multipliers. We first show that the NRP leads naturally to proximal methods with an entropy-like kernel, which is defined by the conjugate of the scaling function, and establish that the two methods are dually equivalent for convex constrained minimization problems. We then study the convergence properties of the nonlinear rescaling algorithm and the corresponding entropy-like proximal methods for convex constrained optimization problems. Special cases of the nonlinear rescaling algorithm are presented. In particular a new class of exponential penalty-modified barrier functions methods is introduced. Partially supported by the National Science Foundation, under Grants DMS-9201297, and DMS-9401871. Partially supported by NASA Grant NAG3-1397 and NSF Grant DMS-9403218.     

Tire track geometry: Variations on a theme

We study closed smooth convex plane curves Λ enjoying the following property: a pair of pointsx, y can traverse Λ so that the distances betweenx andy along the curve and in the ambient plane do not change; such curves are calledbicycle curves. Motivation for this study comes from the problem how to determine the direction of the bicycle motion by the tire tracks of the bicycle wheels; bicycle curves arise in the (rare) situation when one cannot determine which way the bicycle went. We discuss existence and non-existence of bicycle curves, other than circles; in particular, we obtain restrictions on bicycle curves in terms of the ratio of the length of the arcxy to the perimeter, length of Λ, the number and location of their vertices, etc. We also study polygonal analogs of bicycle curves, convex equilateraln-gonsP whosek-diagonals all have equal lengths. For some values ofn andk we prove the rigidity result thatP is a regular polygon, and for some we construct flexible bicycle polygons. Partially supported by an NSF grant.     

The limiting curve of Jarník's polygons

In 1925, Jarník defined a sequence of convex polygons for use in constructing curves containing many lattice points relative to their curvatures. Properly scaled, these polygons converge to a certain limiting curve. In this paper we identify this limiting curve precisely, showing that it consists piecewise of arcs of parabolas, and we discuss the analogous problem for sequences of polygons arising from generalizations of Jarník's construction.

     

Nonlinear successive over-relaxation

Summary We study the convergence of Gauss-Seidel and nonlinear successive overrelaxation methods for finding the minimum of a strictly convex functional defined onR ⁿ .Partially supported by U.S. Army Grant #DAAG29-80-C-0060     

Bernstein-Type Bases and Corner Cutting Algorithms for C 1 Merrien's Curves

Bernstein bases, control polygons and corner-cutting algorithms are defined for C ¹ Merrien's curves introduced in [7]. The convergence of these algorithms is proved for two specific families of curves. Results on monotone and convex interpolants which have been proved in [8] by Merrien and the author are also recovered.     

A generalization of the variation diminishing property

For totally positive matrices, a new variation diminishing property on the sign of consecutive minors is obtained. this property is used to show shape preserving properties of curves generated by totally positive bases and, in particular, of B-spline curves. Partially supported by DGICYT PS93-0310.     

Affine Properties of Convex Equal-Area Polygons

In this paper we discuss some affine properties of convex equal-area polygons, which are convex polygons such that all triangles formed by three consecutive vertices have the same area. Besides being able to approximate closed convex smooth curves almost uniformly with respect to affine length, convex equal-area polygons admit natural definitions of the usual affine differential geometry concepts, like affine normal and affine curvature. These definitions lead to discrete analogous to the six-vertex theorem and an affine isoperimetric inequality. One can also define discrete counterparts of the affine evolute, parallels and the affine distance symmetry set preserving many of the properties valid for smooth curves.     

与给定的多边形相切的闭(C~2-连续)Bézier曲线

Bezier曲线已广泛应用到汽车、航空、造船等许多工业领域中.[1]描述了以给定凸多边形的所有边为切线的.平面三次分段C~2-连续的闭Bezier曲线的构造,并且给出了实际应用. [1]描述的算法有如下缺点:(a)需要解一个大型线性方程组,计算量很大;(b)对     

与给定线段相交的定长线段的运动测度公式及其应用

本文研究了凸多边形的运动测度的表达式,利用线段将已知其包含测度的凸多边形分划成其它的凸多边形,通过计算出与给定线段相交的定长线段的运动测度公式,从而得到某些凸多边形的运动测度的具体表达式,并把它应用到几何概率问题中,获得一个新的几何概率结果.     

On the Structure of Multiple Translational Tilings by Polygonal Regions

We consider polygons with the following ``pairing property': for each edge of the polygon there is precisely one other edge parallel to it. We study the problem of when such a polygon K tiles multiply the plane when translated at the locations Λ , where Λ is a multiset in the plane. The pairing property of K makes this question particularly amenable to Fourier analysis. As a first application of our approach we establish a necessary and sufficient condition for K to tile with a given lattice Λ . (This was first found by Bolle for the case of convex polygons—notice that all convex polygons that tile, necessarily have the pairing property and, therefore, our theorems apply to them.) Our main result is a proof that a large class of such polygons tile multiply only quasi-periodically, which for us means that Λ must be a finite union of translated two-dimensional lattices in the plane. For the particular case of convex polygons we show that all convex polygons which are not parallelograms tile multiply only quasi-periodically, if at all. Received February 24, 1999, and in revised form August 26, 1999, and October 9, 1999.     

Multivariate convexity preserving interpolation by smooth functions

A set of multivariate data is called strictly convex if there exists a strictly convex interpolant to these data. In this paper we characterize strict convexity of Lagrange and Hermite multivariate data by a simple property and show that for strict convex data and given smoothness requirements there exists a smooth strictly convex interpolant. We also show how to construct a multivariate convex smooth interpolant to scattered data. Partially supported by DGICYT PS93-0310 and by the EC project CHRX-CT94-0522.     

Polygons with Parallel Opposite Sides

In this paper we consider convex planar polygons with parallel opposite sides. These polygons can be regarded as discretizations of closed convex planar curves by taking tangent lines at samples with pairwise parallel tangents. For such polygons, we define discrete versions of the area evolute, central symmetry set, equidistants, and area parallels and show that they behave quite similarly to their smooth counterparts.     

A geometric inequality on mixed volumes

We develop some geometric inequality for a kind of generalized convex set. The integral of (n – 2)-th mean curvature of the generalized convex set, the mixed volume of the convex hull of the set, and a reference convex set are involved in the inequality.Partially supported by grants from Kosef and BSRI-95-1419.     

A proximal-based decomposition method for convex minimization problems

This paper presents a decomposition method for solving convex minimization problems. At each iteration, the algorithm computes two proximal steps in the dual variables and one proximal step in the primal variables. We derive this algorithm from Rockafellar's proximal method of multipliers, which involves an augmented Lagrangian with an additional quadratic proximal term. The algorithm preserves the good features of the proximal method of multipliers, with the additional advantage that it leads to a decoupling of the constraints, and is thus suitable for parallel implementation. We allow for computing approximately the proximal minimization steps and we prove that under mild assumptions on the problem's data, the method is globally convergent and at a linear rate. The method is compared with alternating direction type methods and applied to the particular case of minimizing a convex function over a finite intersection of closed convex sets.Corresponding author. Partially supported by Air Force Office of Scientific Research Grant 91-0008 and National Science Foundation Grant DMS-9201297.     

Space-time boundaries for random walks obtained from diffuse measures

We define a “space-time” boundary (referring to space-time harmonic functions) to encompass random walks obtained from compactly supported diffuse measures on Euclidean space, and then prove that in many cases, a qualitative analogue of the Ney-Spitzer theorem (1966) holds, namely that the space-time boundary admits a natural identification with the convex hull of the support of the measure. This can also be interpreted as a generalization to the diffuse case of the weighted moment mapping of algebraic geometry. In many more cases, a weaker analogue holds, identifying the faithful extreme space-time harmonic functions with the interior of the convex body. Partially supported by an operating grant from NSERC (Canada).     

Lattice polygons with two interior lattice points

A lattice point in the plane is a point with integer coordinates. A lattice segment is a line segment whose endpoints are lattice points. A lattice polygon is a simple polygon whose vertices are lattice points. We find all convex lattice polygons in the plane up to equivalence with two interior lattice points.     

Discrete limit theorems for general Dirichlet series. III

Here we prove a limit theorem in the sense of the weak convergence of probability measures in the space of meromorphic functions for a general Dirichlet series. The explicit form of the limit measure in this theorem is given. Partially supported by Lithuanian Foundation of Studies and Science     

New higher-order equiaffine invariants

We introduce new affine invariants for smooth convex bodies. Some sharp affine isoperimetric inequalities are established for the new invariants. Partially supported by an NSERC grant and an FRDP grant. Partially supported by an NSF grant, an FRG-NSF grant and a BSF grant.     

On the mathematics of emergence

We describe a setting where convergence to consensus in a population of autonomous agents can be formally addressed and prove some general results establishing conditions under which such convergence occurs. Both continuous and discrete time are considered and a number of particular examples, notably the way in which a population of animals move together, are considered as particular instances of our setting. This article is based on the 1st Takagi Lectures that the second author delivered at Research Institute for Mathematical Sciences, Kyoto University on November 25 and 26, 2006. Steve Smale Partially supported by an NSF grant.