A short proof of the twelve-point theorem

We present a short elementary proof of the following twelve-point theorem. Let M be a convex polygon with vertices at lattice points, containing a single lattice point in its interior. Denote by m (respectively, m*) the number of lattice points in the boundary of M (respectively, in the boundary of the dual polygon). Then m + m* = 12.Translated from Matematicheskie Zametki, vol. 77, no. 1, 2005, pp. 117–120.Original Russian Text Copyright © 2005 by D. Repov, M. Skopenkov, M. Cencelj.This revised version was published online in April 2005 with a corrected issue number.     

Safety Zone Problem

Given a simple polygon P, its safety zone S (of width δ) is a closed region consisting of straight line segments and circular arcs (of radius δ) bounding the polygon P such that there exists no pair of points p (on the boundary of P) and q (on the boundary of S) having their Euclidean distance d(p, q) less than δ. In this paper we present a linear time algorithm for finding the minimum area safety zone of an arbitrarily shaped simple polygon. It is also shown that our proposed method can easily be modified to compute the Minkowski sum of a simple polygon and a convex polygon in O(MN) time, where M and N are the number of vertices of both the polygons.     

On the dilatation of extremal quasiconformal mappings of polygons

A polygon P _N is the unit disk with distinguished boundary points, . An extremal quasiconformal mapping maps each polygon inscribed in onto a polygon inscribed in . Let f _N be the extremal quasiconformal mapping of P _N onto P' _N. Let K _N be its dilatation and let K ₀ be the maximal dilatation of f ₀. Then, evidently . The problem is, when equality holds. This is completely answered, if f ₀ does not have any essential boundary points. For quadrilaterals Q and Q' = f ₀ (Q) the problem is sup(M'/M) = K ₀, with M and M' the moduli of Q and Q' respectively. Received: December 23, 1997     

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.     

Packing and covering the plane with translates of a convex polygon

A covering of the Euclidean plane by a polygon P is a system of translated copies of P whose union is the plane, and a packing of P in the plane is a system of translated copies of P whose interiors are disjoint. A lattice covering is a covering in which the translates are defined by the points of a lattice, and a lattice packing is defined similarly. We show that, given a convex polygon P with n vertices, the densest lattice packing of P in the plane can be found in O(n) time. We also show that the sparsest lattice covering of the plane by a centrally symmetric convex polygon can be solved in O(n) time. Our approach utilizes results from classical geometry that reduce these packing and covering problems to the problems of finding certain extremal enclosed figures within the polygon.     

Circularm-functions

Circularm-functions are introduced on smooth manifolds with boundary. We study the distribution of their critical circles and construct an example of a four-dimensional manifoldM ⁴ with boundary ∂M ⁴ that satisfies the condition ξ(∂M ⁴)=ξ(M ⁴,∂M ⁴)=0 but does not contain any circularm-function. We prove that a manifold with boundaryM ⁿ (n≥5) such that ξ(∂M ⁿ , ∂M ⁿ )=0 always contains a circularm-function without critical points in the interior manifold. Sukhumi Branch of the Tbilisi University, Sukhumi. Translated from Ukrainskii Matermaticheskii Zhurnal, Vol. 46, No. 6, pp. 776–781, June, 1994.     

A proof of Coleman's conjecture

Almost thirty years ago Coleman made a conjecture that for any convex lattice polygon with v vertices, g (g?1) interior lattice points and b boundary lattice points we have b?2g-v+10. In this note we give a proof of the conjecture. We also aim to describe all convex lattice polygons for which the bound b=2g-v+10 is attained.     

Graphs of Non-Crossing Perfect Matchings

 Let P _n be a set of n=2m points that are the vertices of a convex polygon, and let ℳ _m be the graph having as vertices all the perfect matchings in the point set P _n whose edges are straight line segments and do not cross, and edges joining two perfect matchings M ₁ and M ₂ if M ₂=M ₁−(a,b)−(c,d)+(a,d)+(b,c) for some points a,b,c,d of P _n . We prove the following results about ℳ _m : its diameter is m−1; it is bipartite for every m; the connectivity is equal to m−1; it has no Hamilton path for m odd, m>3; and finally it has a Hamilton cycle for every m even, m≥4. Received: October 10, 2000 Final version received: January 17, 2002 RID="*" ID="*" Partially supported by Proyecto DGES-MEC-PB98-0933 Acknowledgments. We are grateful to the referees for comments that helped to improve the presentation of the paper.     

Realizable Quadruples for Hex-polygons

There are many interesting combinatorial results and problems dealing with lattice polygons, that is, polygons in ℝ² with vertices in the integral lattice ℤ². Geometrically, ℤ² is the set of corners of a tiling of ℝ² by unit squares. Denote by H the set of corners of a tiling of the plane by regular hexagons of unit area and call a polygon P a Hex-polygon or an H-polygon if all vertices of P are in H. Our purpose is to study several combinatorial properties of H-polygons that are analogous to properties of lattice polygons. In particular we aim to find some relationships between the numbers b and i of points from H on the boundary and in the interior of an H-polygon P with the numbers v and c of vertices and the so-called boundary characteristic of P. We also pose three open problems dealing with convex Hex-polygons.     

On the interior lattice points of convex lattice 11-gon

A lattice point in the plane is a point with integer coordinates. A lattice polygon K is a polygon whose vertices are lattice points. In this note we prove that any convex lattice 11-gon contains at least 15 interior lattice points.     

On divergence of series of exponents representing functions regular in convex polygons

We prove that, on a convex polygon, there exist functions from the Smirnov classE whose series of exponents diverge in the metric of the spaceE. Similar facts are established for the convergence almost everywhere on the boundary of a polygon, for the uniform convergence on a closed polygon, and for the pointwise convergence at noncorner points of the boundary.Deceased.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 4, pp. 443–445, April, 1994.     

The Moduli Space of Points in the Boundary of Complex Hyperbolic Space

We consider the space M(n,m)\mathcal{M}(n,m) of ordered m-tuples of distinct points in the boundary of complex hyperbolic n-space, H_\mathbbCⁿ\mathbf{H}_{\mathbb{C}}^{n}, up to its holomorphic isometry group PU(n,1). An important problem in complex hyperbolic geometry is to construct and describe the moduli space for M(n,m)\mathcal{M}(n,m). In particular, this is motivated by the study of the deformation space of complex hyperbolic groups generated by loxodromic elements. In the present paper, we give the complete solution to this problem.     

Steiner polygons in the Steiner problem

A polygon, whose vertices are points in a given setA ofn points, is defined to be a Steiner polygon ofA if all Steiner minimal trees forA lie in it. Cockayne first found that a Steiner polygon can be obtained by repeatedly deleting triangles from the boundary of the convex hull ofA. We generalize this concept and give a method to construct Steiner polygons by repeatedly deletingk-gons,k n. We also prove the uniqueness of Steiner polygons obtained by our method.     

A criterion for finite lattice coverings

For a centrally symmetric convex and a covering lattice L for K, a lattice polygon P is called a covering polygon, if . We prove that P is a covering polygon, if and only if its boundary bd(P) is covered by (L ∩ P) + K. Further we show that this characterization is false for non-symmetric planar convex bodies and in Euclidean d–space, d ≥ 3, even for the unit ball K = B ^d. This revised version was published online in June 2006 with corrections to the Cover Date.     

Pebble Sets in Convex Polygons

Lukács and András posed the problem of showing the existence of a set of n−2 points in the interior of a convex n-gon so that the interior of every triangle determined by three vertices of the polygon contains a unique point of S. Such sets have been called pebble sets by De Loera, Peterson, and Su. We seek to characterize all such sets for any given convex polygon in the plane. We first consider a certain class of pebble sets, called peripheral because they consist of points that lie close to the boundary of the polygon. We characterize all peripheral pebble sets, and show that for regular polygons, these are the only ones. Though we demonstrate examples of polygons where there are other pebble sets, we nevertheless provide a characterization of the kinds of points that can be involved in non-peripheral pebble sets. We furthermore describe algorithms to find such points.     

Preimages of CR submanifolds with generic holomorphic maps

We investigate the notion of CR transversality of a generic holomorphic map f: ℂ ⁿ → ℂ ^m to a smooth CR submanifold M of ℂ ^m . We construct a stratification of the set of non-CR transversal points in the preimage M′ = f ⁻¹ (M) by smooth submanifolds, consisting of points where the CR dimension of M′ is constant. We show the existence of a Whitney stratification for sets which are locally diffeomorphic to the product of an open set and an analytic set. Work on this paper was supported by ARRS, Republic of Slovenia.     

Algorithms for minimum length partitions of polygons

We show that it is possible to find a diagonal partition of anyn-vertex simple polygon into smaller polygons, each of at mostm edges, minimizing the total length of the partitioning diagonals, in timeO(n ³ m ²). We derive the same asymptotic upper time-bound for minimum length diagonal partitions of simple polygons into exactlym-gons provided that the input polygon can be partitioned intom-gons. Also, in the latter case, if the input polygon is convex, we can reduce the upper time-bound toO(n ³ logm).     

Schwarz operators of minimal surfaces spanning polygonal boundary curves

This paper examines the Schwarz operator A and its relatives Ȧ, Ā and Ǡ that are assigned to a minimal surface X which maps consequtive arcs of the boundary of its parameter domain onto the straight lines which are determined by pairs P _j , P _j+1 of two adjacent vertices of some simple closed polygon . In this case X possesses singularities in those boundary points which are mapped onto the vertices of the polygon Γ. Nevertheless it is shown that A and its closure Ā have essentially the same properties as the Schwarz operator assigned to a minimal surface which spans a smooth boundary contour. This result is used by the author to prove in [Jakob, Finiteness of the set of solutions of Plateau’s problem for polygonal boundary curves. I.H.P. Analyse Non-lineaire (in press)] the finiteness of the number of immersed stable minimal surfaces which span an extreme simple closed polygon Γ, and in [Jakob, Local boundedness of the set of solutions of Plateau’s problem for polygonal boundary curves (in press)] even the local boundedness of this number under sufficiently small perturbations of Γ.     

Relations between a manifold and its focal set

Summary Throughout this paper, smooth meansC . All manifolds and embeddings will be smooth. By aclosed m-manifold we mean a compact connected manifold of dimensionm, without boundary.LetM be a closedm-manifold (m>0), andf: ME ⁿ an embedding in Euclideann-space. The focal points off are the centres of principal curvature (with respect to some normal direction) of the embedded manifoldf(M). These points form thefocal set C(f) off.The starting point for our investigation is the following problem. Is there any relation between the topological structure ofM and the relative positions ofC(f) andf(M) inE ⁿ ? In particular, canf be so chosen thatC(f) andf(M) are disjoint? We say that such an embedding isnonfocal.We find that there are manifolds for which no such embedding exists.