Implicit Convex Polygons

Convex polygons in the plane can be defined explicitly as an ordered list of vertices, or given implicitly, for example by a list of linear constraints. The latter representation has been considered in several fields such as facility location, robotics and computer graphics. In this paper, we investigate many fundamental geometric problems for implicitly represented polygons and give simple and fast algorithms that are easy to implement. We uncover an interesting partition of the problems into two classes: those that exhibit an (nlogn) lower bound on their complexity, and those that yield O(n) time algorithms via prune-and-search methods.     

Refolding Planar Polygons

This paper describes an algorithm for generating a guaranteed intersection-free interpolation sequence between any pair of compatible polygons. Our algorithm builds on prior results from linkage unfolding, and if desired it can ensure that every edge length changes monotonically over the course of the interpolation sequence. The computational machinery that ensures against self-intersection is independent from a distance metric that determines the overall character of the interpolation sequence. This decoupled approach provides a powerful control mechanism for determining how the interpolation should appear, while still assuring against intersection and guaranteeing termination of the algorithm. Our algorithm also allows additional control by accommodating a set of algebraic constraints that can be weakly enforced throughout the interpolation sequence.     

Robust Tensegrity Polygons

A tensegrity polygon is a planar cable-strut tensegrity framework in which the cables form a convex polygon containing all vertices. The underlying edge-labeled graph $T=(V;C,S)$ T = ( V ; C , S ) , in which the cable edges form a Hamilton cycle, is an abstract tensegrity polygon. It is said to be robust if every convex realization of T as a tensegrity polygon has an equilibrium stress which is positive on the cables and negative on the struts, or equivalently, if every convex realization of T is infinitesimally rigid. We characterize the robust abstract tensegrity polygons on n vertices with $n-2$ n - 2 struts, answering a question of Roth and Whiteley (Trans Am Math Soc 265:419–446, 1981) and solving an open problem of Connelly (Recent progress in rigidity theory, 2008).     

Sporadic Reinhardt Polygons

Let $n$ be a positive integer, not a power of two. A Reinhardt polygon is a convex $n$ -gon that is optimal in three different geometric optimization problems: it has maximal perimeter relative to its diameter, maximal width relative to its diameter, and maximal width relative to its perimeter. For almost all $n$ , there are many Reinhardt polygons with $n$ sides, and many of them exhibit a particular periodic structure. While these periodic polygons are well understood, for certain values of $n$ , additional Reinhardt polygons exist, which do not possess this structured form. We call these polygons sporadic. We completely characterize the integers $n$ for which sporadic Reinhardt polygons exist, showing that these polygons occur precisely when $n=pqr$ with $p$ and $q$ distinct odd primes and $r\ge 2$ . We also prove that a positive proportion of the Reinhardt polygons with $n$ sides is sporadic for almost all integers $n$ , and we investigate the precise number of sporadic Reinhardt polygons that are produced for several values of $n$ by a construction that we introduce.     

Circles and Polygons

We consider the Money–Coutts process. We show that in parallelograms this process is always preperiodic while the process is chaotic for an open set of quadrilaterals.     

Morphing Simple Polygons

In this paper we investigate the problem of morphing (i.e., continuously deforming) one simple polygon into another. We assume that our two initial polygons have the same number of sides n , and that corresponding sides are parallel. We show that a morph is always possible through an interpolating simple polygon whose n sides vary but stay parallel to those of the two original ones. If we consider a uniform scaling or translation of part of the polygon as an atomic morphing step, then we show that O(n log n) such steps are sufficient for the morph. Furthermore, the sequence of steps can be computed in O(n log n) time. Received May 25, 1999, and in revised form November 15, 1999.     

Slim Near Polygons

In this paper we initiate the study of hybrid slim near hexagons. These are near hexagons which are not dense and not a generalized hexagon in which each line is incident with exactly three points. In the present paper, we will emphasize slim near hexagons with at least one W(2)-quad or Q(5, 2)-quad. Such near hexagons are finite if there are no special points, i.e. points which lie at distance at most 2 from any other point. We will determine upper bounds for the number of lines through a fixed point. We will also look at the special case where the near hexagon has an order. We will determine all slim near hexagons with an order which contain at least one (necessarily big) Q(5,2)-quad, or at least one big W(2)-quad.AMS Classification 05B25, 51E12Communicated by: M.J. de ResminiPostdoctoral Fellow of the Research Foundation–Flanders.     

Decomposable Near Polygons

We give a common construction for the product and the glued near polygons by generalizing the glueing construction given in [5]. We call the near polygons arising from this generalized glueing construction decomposable or (again) glued. We will study the geodetically closed sub near polygons of decomposable near polygons. Each decomposable near hexagon has a nice pair of partitions in geodetically closed near polygons. We will give a characterization of the decomposable near polygons using this property.     

Bénard Polygons

We prove that if a neighborhood of a polygonal region admits a two-dimensional eigenfunction of the Laplacian, having a nonzero eigenvalue and such that its normal derivative vanishes on all the bounding edges, then the polygonal region must be a union of complete pieces of a tiling of the plane by congruent rectangles, or by congruent (45°, 45°, 90°) or (30°, 60°, 90°) triangles. Hydrodynamically, this means that during critical convection in a horizontal fluid layer uniformally heated from below, the mere occurrence of one arbitrary closed vertical polygonal fluid surface across which there is no transportation of fluid automatically guarantees the presence of one of the usual special convection patterns. In addition it shows that linear convection theory seldom predicts a regular fluid pattern: e.g., for the case of a triangular container having angles substantially different from (45°, 45°, 90°), (30°, 60°, 90°), (60°, 60°, 60°) or (30°, 30°, 120°), it predicts that the convection cells not touching the boundary, if any, should be noticeably nonpolygonal. We also consider a nonlinear generalization and the noneuclidean analogues of such polygons.     

Heat Flow from Polygons

Potential Analysis - We study the heat flow from an open, bounded set D in $mathbb {R}^{2}$ with a polygonal boundary ?D. The initial condition is the indicator function of D. A Dirichlet 0...     

Extended Formulations for Polygons

The extension complexity of a polytope?P is the smallest integer?k such that?P is the projection of a polytope?Q with?k facets. We study the extension complexity of n-gons in the plane. First, we give a new proof that the extension complexity of regular n-gons is O(logn), a result originating from work by Ben-Tal and Nemirovski (Math. Oper. Res. 26(2), 193?C205, 2001). Our proof easily generalizes to other permutahedra and simplifies proofs of recent results by Goemans (2009), and Kaibel and Pashkovich (2011). Second, we prove a lower bound of $\sqrt{2n}$ on the extension complexity of generic n-gons. Finally, we prove that there exist n-gons whose vertices lie on an O(n)×O(n ²) integer grid with extension complexity $\varOmega (\sqrt{n}/\sqrt{\log n})$ .     

Polygons Needing Many Flipturns

A flipturn on a polygon consists of reversing the order of edges inside a pocket of the polygon, without changing lengths or slopes. Any polygon with n edges must be convexified after at most (n − 1)! flipturns. A recent paper showed that in fact it will be convex after at most n(n−3)/2 flipturns.We give here lower bounds.We construct a polygon such that if pockets are chosen in a bad way, at least (n − 2)²/4 flipturns are needed to convexify the polygon. In another construction, (n −1)²/8 flipturns are needed, regardless of the order in which pockets are chosen. All our bounds are adaptive to a pre-specified number of distinct slopes of the edges.     

Untangling Polygons and Graphs

Untangling is a process in which some vertices in a drawing of a planar graph are moved to obtain a straight-line plane drawing. The aim is to move as few vertices as possible. We present an algorithm that untangles the cycle graph C _n while keeping Ω(n ^2/3) vertices fixed. For any connected graph G, we also present an upper bound on the number of fixed vertices in the worst case. The bound is a function of the number of vertices, maximum degree, and diameter of G. One consequence is that every 3-connected planar graph has a drawing δ such that at most O((nlog n)^2/3) vertices are fixed in every untangling of δ.     

Convex Polygons are Cover-Decomposable

We show that for any open convex polygon P, there is a constant k(P) such that any k(P)-fold covering of the plane with translates of P can be decomposed into two coverings.     

Polygons in billiard orbits

We study the geometry of billiard orbits on rectangular billiards. A truncated billiard orbit induces a partition of the rectangle into polygons. We prove that thirteen is a sharp upper bound for the number of different areas of these polygons.     

Acute Triangulations of Polygons

This paper proposes a combinatorial approach to planning non-colliding trajectories for a polygonal bar-and-joint framework with n vertices. It is based on a new class of simple motions induced by expansive one-degree-of-freedom mechanisms, which guarantee noncollisions by moving all points away from each other. Their combinatorial structure is captured by pointed pseudo-triangulations, a class of embedded planar graphs for which we give several equivalent characterizations and exhibit rich rigidity theoretic properties. The main application is an efficient algorithm for the Carpenter’s Rule Problem: convexify a simple bar-and-joint planar polygonal linkage using only non-self-intersecting planar motions. A step of the algorithm consists in moving a pseudo-triangulation-based mechanism along its unique trajectory in configuration space until two adjacent edges align. At the alignment event, a local alteration restores the pseudo-triangulation. The motion continues for O(n3) steps until all the points are in convex position. An erratum to this article is available at .     

Isodiametric Problems for Polygons

The maximal area of a polygon with n = 2m edges and unit diameter is not known when m ≥ 5, nor is the maximal perimeter of a convex polygon with n = 2^m edges and unit diameter known when m ≥ 4. We construct improved polygons in both problems, and show that the values we obtain cannot be improved for large n by more than c₁/n³ in the area problem and c₂/n⁵ in the perimeter problem, for certain constants c₁ and c₂.     

Dynamic Geometry of Polygons

---

Dynamic Geometry of Polygons

     

Frobenius Quasigroups and Regular Polygons

In terms of regular n-gons a left distributive quasigroup operation is defined on the complex plane. This operation can be expressed by means of a semidirect product G of the translation group (which is sharply transitive on the points of the plane and hence may be identified with the plane) by a finite cyclic group of rotations of order n. That observation makes possible a wide generalization of this geometric quasigroup construction. The connection in general between algebraic properties of the quasigroup and various properties of the group G is discussed, in particular it is studied what the consequences for the quasigroup Q are if G is interpreted as a topological group or an algebraic group.