Template-controlled reactivity: Following nature's way to design and construct metal-organic polyhedra and polygons

We show how a template-controlled reaction performed in the organic solid state can be used to construct a molecule that functions as an organic building unit of both a metal-organic polyhedron and polygon. The template is a small organic molecule that organizes two olefins via hydrogen bonds for a [2+2] photodimerization. The process of utilizing a molecule to build a molecule that is subsequently used for self-assembly is inspired by the general two-step process of template-directed synthesis and self-assembly of Nature that is used to construct large, functional self-assembled structures.     

On the stability of the polygonal isoperimetric inequality

We obtain a sharp lower bound on the isoperimetric deficit of a general polygon in terms of the variance of its side lengths, the variance of its radii, and its deviation from being convex. Our technique involves a functional minimization problem on a suitably constructed compact manifold and is based on the spectral theory for circulant matrices.     

A discrete four vertex theorem

A discrete four vertex theorem is proved for a general plane polygon using a method of proof that also yields a proof, that appears to be new, for the classical four vertex theorem.     

The point in polygon problem for arbitrary polygons

A detailed discussion of the point in polygon problem for arbitrary polygons is given. Two concepts for solving this problem are known in literature: the even–odd rule and the winding number, the former leading to ray-crossing, the latter to angle summation algorithms. First we show by mathematical means that both concepts are very closely related, thereby developing a first version of an algorithm for determining the winding number. Then we examine how to accelerate this algorithm and how to handle special cases. Furthermore we compare these algorithms with those found in literature and discuss the results.     

The Erdős–Nagy theorem and its ramifications

Given a simple polygon in the plane, a flip is defined as follows: consider the convex hull of the polygon. If there are no pockets do not perform a flip. If there are pockets then reflect one pocket across its line of support of the polygon to obtain a new simple polygon. In 1934 Paul Erdős introduced the problem of repeatedly flipping all the pockets of a simple polygon simultaneously and he conjectured that the polygon would become convex after a finite number of flips. In 1939 Béla Nagy proved that if at each step only one pocket is flipped the polygon will become convex after a finite number of flips. The history of this problem is reviewed, and a simple elementary proof is given of a stronger version of the theorem. Variants, generalizations, and applications of the theorem of interest in computational knot theory, polymer physics and molecular biology are discussed. Several results in the literature are improved with the application of the theorem. For example, Grünbaum and Zaks recently showed that even non-simple (self-crossing) polygons may be convexified in a finite number of suitable flips. Their flips each take Θ(n²) time to determine. A simpler proof of this result is given that yields an algorithm that takes O(n) time to determine each flip. In the context of knot theory Millet proposed an algorithm for convexifying equilateral polygons in 3-dimensions with a generalization of a flip called a pivot. Here Millet's algorithm is generalized so that it works also in dimensions higher than three and for polygons containing edges with arbitrary lengths. A list of open problems is included.     

Correction: Generalized Polygons with Highly Transitive Collineation Groups

In Geom Dedicata 58 (1995), 91–100, the author tried to classify generalized quadrangles with a collineation group acting transitively on ordered pentagons. Unfortunately, this paper contains several mistakes. The main result is affected such that there now is an additional compact connected quadrangle (and its dual) with a 5-gon transitive group. I am indebted to Martin Wolfrom who pointed out the error and offered a correction.     

Inapproximability of finding maximum hidden sets on polygons and terrains

How many people can hide in a given terrain, without any two of them seeing each other? We are interested in finding the precise number and an optimal placement of people to be hidden, given a terrain with n vertices. In this paper, we show that this is not at all easy: The problem of placing a maximum number of hiding people is almost as hard to approximate as the problem, i.e., it cannot be approximated by any polynomial-time algorithm with an approximation ratio of n for some >0, unless P=NP. This is already true for a simple polygon with holes (instead of a terrain). If we do not allow holes in the polygon, we show that there is a constant >0 such that the problem cannot be approximated with an approximation ratio of 1+.     

Triangulations (tilings) and certain block triangular matrices

For a convex polygonP withn sides, a ‘partitioning’ ofP inton−2 nonoverlapping triangles each of whose vertices is a vertex ofP is called a triangulation or tiling, and each triangle is a tile. Each tile has a given cost associated with it which may differ one from another. This paper considers the problem of finding a tiling ofP such that the sum of the costs of the tiles used is a minimum, and explores the curiosity that (an abstract formulation of) it can be cast as a linear program. Further the special structure of the linear program permits a recursive O(n ³) algorithm. Research and reproduction of this report were partially supported by the National Science Foundation Grants MCS-8119774, MCS-7926009 and ECS-8012974; Department of Energy Contract DE-AM03-76SF00326, PA# DE-AT03-76ER72018; Office of Naval Research Contract N00014-75-C-0267. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the author(s) and donot necessarily reflect the views of the above sponsors.     

A Besov Space Mapping Property for the Double Layer Potential on Polygons

A classical boundedness property for the double layer potential on polygons with respect to Sobolev spaces is extended to a scale of Besov spaces which is related to adaptive restricted nonlinear approximation schemes.     

Draining a polygon—or—rolling a ball out of a polygon

We introduce the problem of draining water (or balls representing water drops) out of a punctured polygon (or a polyhedron) by rotating the shape. For 2D polygons, we obtain combinatorial bounds on the number of holes needed, both for arbitrary polygons and for special classes of polygons. We detail an $O(n^2\log n)$ algorithm that finds the minimum number of holes needed for a given polygon, and argue that the complexity remains polynomial for polyhedra in 3D. We make a start at characterizing the 1-drainable shapes, those that only need one hole.