Asymptotics of random convex polygonal lines

The present paper deals with the limit shape of random plane convex polygonal lines whose edges are independent and identically distributed, with finite first moment. The smoothness of a limit curve depends on some properties of the distribution. The limit curve is determined by the projection of the distribution to the unit circle. This correspondence between limit curves and measures on the unit circle is proved to be a bijection. The emphasis is on limit distributions of deviations of random polygonal lines from a limit curve. Normed differences of Minkowski support functions converge to a Gaussian limit process. The covariance of this process can be found in terms of the initial distribution. In the case of uniform distribution on the unit circle, a formula for the covariance is found. The main result is that a.s. sample functions of the limit process have continuous first derivative satisfying the Hölder condition of order a, for any fixed a with 0相似文献   

Optimizing a constrained convex polygonal annulus

In this paper we give solutions to several constrained polygon annulus placement problems for offset and scaled polygons, providing new efficient primitive operations for computational metrology and dimensional tolerancing. Given a convex polygon P and a planar point set S, the goal is to find the thinnest annulus region of P containing S. Depending on the application, there are several ways this problem can be constrained. In the variants that we address the size of the polygon defining the inner (respectively, outer) boundary of the annulus is fixed, and the annulus is minimized by minimizing (respectively, maximizing) the outer (respectively, inner) boundary. We also provide solutions to a related known problem: finding the smallest homothetic copy of a polygon containing a set of points. For all of these problems, we solve for the cases where smallest and largest are defined by either the offsetting or scaling of a polygon. We also provide some experimental results from implementations of several competing approaches to a primitive operation important to all the above variants: finding the intersection of n copies of a convex polygon.     

On a plane convex arc with a large number of lattice points

  A convex are on which there are at least M ^{log 2/log 3} rational points of the form (u/M, v/M) is constructed. Bibliography: 10 titles. Translated from Zapiski Nauchnykh Semiriarov POMI, Vol. 357, 2008, pp. 22–32.     

The number of lattice points on a convex curve

If C is a strictly convex plane curve of length l, it has been known for a long time that the number of integer lattice points on C is $\text{O(l}{}^{\mathrm{<mtext>2</mtext><mtext>3</mtext>}}\text{)}$ and the exponent is best possible. In this paper, it is shown that the exponent can be decreased by imposing suitable smoothness conditions on C; in particular, if C has a continuous third derivative with a sensible bound, the best possible value of the exponent lies between $\text{3}\text{5}$ and $\text{1}\text{3}$ inclusive.     

On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space

We show that the number of critical positions of a convex polygonal objectB moving amidst polygonal barriers in two-dimensional space, at which it makes three simultaneous contacts with the obstacles but does not penetrate into any obstacle isO(kn _s (kn)) for somes6, wherek is the number of boundary segments ofB,n is the number of wall segments, and _s (q) is an almost linear function ofq yielding the maximal number of breakpoints along the lower envelope (i.e., pointwise minimum) of a set ofq continuous functions each pair of which intersect in at mosts points (here a breakpoint is a point at which two of the functions simultaneously attain the minimum). We also present an example where the number of such critical contacts is (k ² n ²), showing that in the worst case our upper bound is almost optimal.Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation.     

On convex bodies containing a given number of lattice points

Given a convex body K in Euclidean space, a necessary and sufficient condition is established in order that for each n there exists a homothetic copy of K containing exactly n lattice points. Similar theorems are proved for congruent copies of K and for discrete sets other than lattices.     

Nine convex sets determine a pentagon with convex sets as vertices

It is proved that if ℱ is a family of nine pairwise disjoint compact convex sets in the plane such that no member of ℱ is contained in the convex hull of the union of two other sets of ℱ, then ℱ has a subfamily ℱ′ with five elements such that no member of ℱ′ is contained in the convex hull of the union of the other sets of ℱ′.     

Finding all vertices of a convex polyhedron

Summary The paper describes an algorithm for finding all vertices of a convex polyhedron defined by a system of linear equations and by non-negativity conditions for variables. The algorithm is described using terminology of the theory of graphs and it seems to provide a computationally effective method. An illustrative example and some experiences with computations on a computer are given.     

Point-color-symmetric graphs with a prime number of vertices

We construct and enumerate all point-color-symmetric digraphs and graphs with a prime number of vertices. Our result unifies and generalizes the similar results for vertex transitive graphs and symmetric graphs.     

Nonflexible polyhedra with a small number of vertices

The paper shows which embedded and immersed polyhedra with no more than eight vertices are nonflexible. It turns out that all embedded polyhedra are nonflexible, except possibly for polyhedra of one of the combinatorial types, for which the problem still remains open. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 12, No. 1, pp. 143–165, 2006.     

On the number of singularities,zero curvature points and vertices of a simple convex space curve

We prove a generalization of the 4 vertex theorem forC ³ closed simple convex space curves including singular and zero curvature points.Work partially supported by CNPq. The second author is also grateful to the Universidade Federal de Viçosa (Brasil) for hospitality during the production of this work.     

An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space

We present an efficient algorithm for planning the motion of a convex polygonal bodyB in two-dimensional space bounded by a collection of polygonal obstacles. Our algorithm extends and combines the techniques of Leven and Sharir and of Sifrony and Sharir used for the case in whichB is a line segment (a ladder). It also makes use of the results of Kedem and Sharir on the planning of translational motion ofB amidst polygonal obstacles, and of a recent result of Leven and Sharir on the number of free critical contacts ofB with such polygonal obstacles. The algorithm runs in timeO(kn ₆(kn) logkn), wherek is the number of sides ofB, n is the number of obstacle edges, and ,(q) is an almost linear function ofq yielding the maximal number of connected portions ofq continuous functions which compose the graph of their lower envelope, where it is assumed that each pair of these functions intersect in at mosts points.Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation.     

On labeled vertex-transitive digraphs with a prime number of vertices

We enumerate, up to isomorphism, several classes of labeled vertex-transitive digraphs with a prime number of vertices.