Affinely Regular Polygons as Extremals of Area Functionals

For any convex n-gon P we consider the polygons obtained by dropping a vertex or an edge of P. The area distance of P to such (n−1)-gons, divided by the area of P, is an affinely invariant functional on n-gons whose maximizers coincide with the affinely regular polygons. We provide a complete proof of this result. We extend these area functionals to planar convex bodies and we present connections with the affine isoperimetric inequality and parallel X-ray tomography.     

On the number of disjoint convex quadrilaterals for a planar point set

For a given planar point set P, consider a partition of P into disjoint convex polygons. In this paper, we estimate the maximum number of convex quadrilaterals in all partitions.     

Regular Steiner polygons

The symmetric difference area functional is minimized for a pair of planar convex polygons. Two solution procedures are outlined: a direct constructive methodology and a support function formulation. Examples illustrate the solution methodology.     

The mean value of the area of polygons circumscribed about a plane convex body

Inner parallel bodies are used to prove that the mean area of polygons circumscribed about a convex bodyK of given area is minimum whenK is a circle.     

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.     

Decompositions,Partitions, and Coverings with Convex Polygons and Pseudo-Triangles

We propose a novel subdivision of the plane that consists of both convex polygons and pseudo-triangles. This pseudo-convex decomposition is significantly sparser than either convex decompositions or pseudo-triangulations for planar point sets and simple polygons. We also introduce pseudo-convex partitions and coverings. We establish some basic properties and give combinatorial bounds on their complexity. Our upper bounds depend on new Ramsey-type results concerning disjoint empty convex k-gons in point sets.     

An efficient algorithm for the computation of the metric average of two intersecting convex polygons, with application to morphing

Motivated by the method for the reconstruction of 3D objects from a set of parallel cross sections, based on the binary operation between 2D sets termed “metric average”, we developed an algorithm for the computation of the metric average between two intersecting convex polygons in 2D. For two 1D sets there is an algorithm for the computation of the metric average, with linear time in the number of intervals in the two 1D sets. The proposed algorithm has linear computation time in the number of vertices of the two polygons. As an application of this algorithm, a new technique for morphing between two convex polygons is developed. The new algorithm performs morphing in a non-intuitive way.     

Reconstructing Convex Polygons in the Plane from One Directed X-Ray

Gardner [7] proved that with the exception of a simple class of nonparallel wedges, convex polygons in the plane are uniquely determined by one directed X-ray. This paper develops methods for reconstructing convex polygons in the plane from one directed X-ray. We show that nonsmooth points on the boundary of a convex body are located along rays where the derivative of the data have a jump discontinuity. Location of the nonsmooth points divides a convex polygon into a finite set of wedges. We prove uniqueness theorems and give algorithms for reconstructing nonparallel wedges from line integrals along four or more rays. Also, we characterize discrete data sets that are directed X-rays of both parallel and nonparallel wedges. Several examples of reconstructions are included. Received August 16, 1999, and in revised form September 13, 2000. Online publication May 4, 2001.     

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.     

The parallel volume at large distances

In this paper we examine the asymptotic behavior of the parallel volume of planar non-convex bodies as the distance tends to infinity. We show that the difference between the parallel volume of the convex hull of a body and the parallel volume of the body itself tends to 0. This yields a new proof for the fact that a planar body can only have polynomial parallel volume if it is convex. Extensions to Minkowski spaces and random sets are also discussed.     

Convex drawings of hierarchical planar graphs and clustered planar graphs

In this paper, we present results on convex drawings of hierarchical graphs and clustered graphs. A convex drawing is a planar straight-line drawing of a plane graph, where every facial cycle is drawn as a convex polygon. Hierarchical graphs and clustered graphs are useful graph models with structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures.We first present the necessary and sufficient conditions for a hierarchical plane graph to admit a convex drawing. More specifically, we show that the necessary and sufficient conditions for a biconnected plane graph due to Thomassen [C. Thomassen, Plane representations of graphs, in: J.A. Bondy, U.S.R. Murty (Eds.), Progress in Graph Theory, Academic Press, 1984, pp. 43–69] remains valid for the case of a hierarchical plane graph. We then prove that every internally triconnected clustered plane graph with a completely connected clustering structure admits a “fully convex drawing,” a planar straight-line drawing such that both clusters and facial cycles are drawn as convex polygons. We also present algorithms to construct such convex drawings of hierarchical graphs and clustered graphs.     

A decomposition theorem for convexity spaces

We utilize the unifying framework of families of convexity spaces for the treatment of various notions of planar convexity and the associated convex hulls. Our major goal is to prove the refinement and decomposition theorems for families of convexity spaces. These general theorems are then applied to two examples: restricted-oriented convex sets andNESW-convex sets. The applications demonstrate the usefulness of these general theorems, since they give rise to simple algorithms for the computation of the associated convex hulls of polygons.     

On ordinary points in arrangements

We show that in an arrangement ofn curves in the plane (or on the sphere) there are at leastn/2 points where precisely 2 curves cross (ordinary points). Furthermore there are at least (4/3)n triangular regions in the complex determined by the arrangement. Triangular regions and ordinary vertices are both connected with boundary vertices of certain distinguished subcomplexes. By analogy with rectilinear planar polygons we distinguish concave and convex vertices of these subcomplexes. Our lower bounds arise from lower bounds for convex vertices in the distinguished subcomplexes.     

Dimers, tilings and trees

Generalizing results of Temperley (London Mathematical Society Lecture Notes Series 13 (1974) 202), Brooks et al. (Duke Math. J. 7 (1940) 312) and others (Electron. J. Combin. 7 (2000); Israel J. Math. 105 (1998) 61) we describe a natural equivalence between three planar objects: weighted bipartite planar graphs; planar Markov chains; and tilings with convex polygons. This equivalence provides a measure-preserving bijection between dimer coverings of a weighted bipartite planar graph and spanning trees of the corresponding Markov chain. The tilings correspond to harmonic functions on the Markov chain and to “discrete analytic functions” on the bipartite graph.The equivalence is extended to infinite periodic graphs, and we classify the resulting “almost periodic” tilings and harmonic functions.     

Computing Cartograms with Optimal Complexity

In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons, while edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight. The complexity of a cartogram is determined by the maximum number of corners (or sides) required for any polygon. In a series of papers the polygonal complexity of such representations for maximal planar graphs has been reduced from the initial 40 to 34, then to 12 and very recently to the currently best known 10. Here we describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity as 8-sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine it into an area-universal rectangular layout in linear time. The exact cartogram can be computed from the area-universal layout with numerical iteration, or can be approximated with a hill-climbing heuristic. We also describe an alternative construction of cartograms for Hamiltonian maximal planar graphs, which allows us to directly compute the cartograms in linear time. Moreover, we prove that even for Hamiltonian graphs 8-sided rectilinear polygons are necessary, by constructing a non-trivial lower bound example. The complexity of the cartograms can be reduced to 6 if the Hamiltonian path has the extra property that it is one-legged, as in outer-planar graphs. Thus, we have optimal representations (in terms of both polygonal complexity and running time) for Hamiltonian maximal planar and maximal outer-planar graphs. Finally we address the problem of constructing small-complexity cartograms for 4-connected graphs (which are Hamiltonian). We first disprove a conjecture, posed by two set of authors, that any 4-connected maximal planar graph has a one-legged Hamiltonian cycle, thereby invalidating an attempt to achieve a polygonal complexity 6 in cartograms for this graph class. We also prove that it is NP-hard to decide whether a given 4-connected plane graph admits a cartogram with respect to a given weight function.     

Geodesic Universal Molecules

The first phase of TreeMaker, a well-known method for origami design, decomposes a planar polygon (the “paper”) into regions. If some region is not convex, TreeMaker indicates it with an error message and stops. Otherwise, a second phases is invoked which computes a crease pattern called a “universal molecule”. In this paper we introduce and study geodesic universal molecules, which also work with non-convex polygons and thus extend the applicability of the TreeMaker method. We characterize the family of disk-like surfaces, crease patterns and folded states produced by our generalized algorithm. They include non-convex polygons drawn on the surface of an intrinsically flat piecewise-linear surface which have self-overlap when laid open flat, as well as surfaces with negative curvature at a boundary vertex.     

Numerical construction of Nash and Stackelberg solutions in a two-player linear non-zero-sum positional differential game

Numerical methods are proposed for constructing Nash and Stackelberg solutions in a two-player linear non-zero-sum positional differential game with terminal cost functionals and geometric constraints on the players’ controls. The formalization of the players’ strategies and of the motions generated by them is based on the formalization and results from the theory of positional zero-sum differential games developed by N.N. Krasovskii and his school. It is assumed that the game is reduced to a planar game and the constraints on the players’ controls are given in the form of convex polygons. The problem of finding solutions of the game may be reduced to solving nonstandard optimal control problems. Several computational geometry algorithms are used to construct approximate trajectories in these problems, in particular, algorithms for constructing the convex hull as well as the union, intersection, and algebraic sum of polygons.     

On fencing problems

Fencing problems regard the bisection of a convex body in a way that some geometric measures are optimized. We introduce the notion of relative diameter and study bisections of centrally symmetric planar convex bodies, bisections by straight line cuts in general planar convex bodies and also bisections by hyperplane cuts for convex bodies in higher dimensions. In the planar case we obtain the best possible lower bound for the ratio between the relative diameter and the area.     

On the X-Y convex hull of a set of X-Y polygons

We study the class of rectilinear polygons, calledX – Y polygons, with horizontal and vertical edges, which are frequently used as building blocks for very large-scale integrated (VLSI) circuit layout and wiring. In the paper we introduce the notion of convexity within the class ofX – Y polygons and present efficient algorithms for computing theX – Y convex hulls of anX – Y polygon and of a set ofX – Y polygons under various conditions. Unlike convex hulls in the Euclidean plane, theX – Y convex hull of a set ofX – Y polygons may not exist. The condition under which theX – Y convex hull exists is given and an algorithm for testing if the given set ofX – Y polygons satisfies the condition is also presented.     

Variations on R. Schwartz��s Inequality for the Schwarzian Derivative

R. Schwartz??s inequality provides an upper bound for the Schwarzian derivative of a parameterization of a circle in the complex plane and on the potential of Hill??s equation with coexisting periodic solutions. We prove a discrete version of this inequality and obtain a version of the planar Blaschke?CSantalo inequality for not necessarily convex polygons. In the proof, we use some formulas from the theory of frieze patterns. We consider a centro-affine analog of Lük???s inequality for the average squared length of a chord subtending a fixed arc length of a curve??the role of the squared length played by the area??and prove that the central ellipses are local minima of the respective functionals on the space of star-shaped centrally symmetric curves. We conjecture that the central ellipses are global minima. In an appendix, we relate the Blaschke?CSantalo and Mahler inequalities with the asymptotic dynamics of outer billiards at infinity.