A P‐Completeness Result for Visibility Graphs of Simple Polygons

For each vertex of a simple polygon P an integer valued weight is given. We consider the path p₁, p₂, ..., p_k in P which is created according to the following strategy: p₁ is a designated start vertex s and p_i+1 is obtained by choosing the vertex with smallest weight among all vertices visible from p_i and different from p₁, p₂, ..., p_i. If there is no such vertex the path is finished. This path is called geometric lexicographic dead end path. We shall prove the problem of determining whether a distinguished vertex t of P is on the geometric lexicographic dead end path or not to be P‐complete.     

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.     

Hierarchical Decompositions and Circular Ray Shooting in Simple Polygons

A hierarchical decomposition of a simple polygon is introduced. The hierarchy has logarithmic depth, linear size, and its regions have at most three neighbors. Using this hierarchy, circular ray shooting queries in a simple polygon on n vertices can be answered in O(log² n) query time and O(n log n) space. If the radius of the circle is fixed, the query time can be improved to O(log n) and the space to O(n).     

Minimizing the Size of Vertexlights in Simple Polygons

We show that given a simple Polygon P it is NP‐hard to determine the smallest α ∈ [0, π] such that P can be illuminated by α‐vertexlights, if we place exactly one α‐vertexlight in each vertex of P.     

Minkowski Sums of Monotone and General Simple Polygons

Let P be a simple polygon with m edges, which is the disjoint union of k simple polygons, all monotone in a common direction u, and let Q be another simple polygon with n edges, which is the disjoint union of ℓ simple polygons, all monotone in a common direction v. We show that the combinatorial complexity of the Minkowski sum P ⊕ Q is O(kℓmnα(min{m,n})), where α(·) is the inverse Ackermann function. Some structural properties of the case k = ℓ = 1 have been (implicitly) studied in [17]. We rederive these properties using a different proof, apply them to obtain the above complexity bound for k = ℓ = 1, obtain several additional properties of the sum for this special case, and then use them to derive the general bound.     

Allocating Vertex π-Guards in Simple Polygons via Pseudo-Triangulations

We use the concept of pointed pseudo-triangulations to establish new upper and lower bounds on a well known problem from the area of art galleries: What is the worst case optimal number of vertex π-guards that collectively monitor a simple polygon with n vertices? Our results are as follows: (1) Any simple polygon with n vertices can be monitored by at most \lfloor n/2 \rfloor general vertex π-guards. This bound is tight up to an additive constant of 1. (2) Any simple polygon with n vertices, k of which are convex, can be monitored by at most \lfloor (2n – k)/3 \rfloor edge-aligned vertexπ-guards. This is the first non-trivial upper bound for this problem and it is tight for the worst case families of polygons known so far.     

Simple Polygons of Maximum Perimeter Contained in a Unit Disk

A polygon is said to be simple if the only points of the plane belonging to two of its edges are its vertices. We answer the question of finding, for a given integer n, a simple n-sided polygon contained in a disk of radius 1 that has the longest perimeter. When n is even, the optimal solution is arbitrarily close to a line segment of length 2n. When n is odd, the optimal solution is arbitrarily close to an isosceles triangle. Work of the first author was supported by NSERC grant 239436-05, AFOSR FA9550-07-1-0302, and ExxonMobil. Work of the second author was supported by NSERC grant 105574-02.     

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.     

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.     

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 δ.     

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.     

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.     

Hyperbolic Polygons and Real Schottky Groups

In a work due to Aigon and Silhol (also Buser and Silhol) a construction of 10 genus two closed Riemann surfaces is done from a given right angled hyperbolic pentagon. In this note we construct real Schottky groups uniformizations of the corresponding constructions. In particular, we are able to write down the algebraic curves obtained in the above work in terms of the parameters of the real Schottky group. We generalize such a construction for any right angled hyperbolic polygon and also consider an example for a nonright angled pentagon in the last section.     

Polygons in Buildings and their Refined Side Lengths

As in a symmetric space of noncompact type, one can associate to an oriented geodesic segment in a Euclidean building a vector valued length in the Euclidean Weyl chamber Δ _euc . In addition to the metric length it contains information on the direction of the segment. In this paper we study restrictions on the Δ _euc -valued side lengths of polygons in Euclidean buildings. The main result is that for thick Euclidean buildings X the set Pn(X){\mathcal{P}n(X)} of possible Δ _euc -valued side lengths of oriented n-gons depends only on the associated spherical Coxeter complex. We show moreover that it coincides with the space of Δ _euc -valued weights of semistable weighted configurations on the Tits boundary ∂ _Tits X. The side lengths of polygons in symmetric spaces of noncompact type are studied in the related paper [KLM1]. Applications of the geometric results in both papers to algebraic group theory are given in [KLM2].     

Dynamic Polygons and the Graphing Calculator

A match stick puzzle is used as a springboard for a secondary classroom investigation into mathematical modeling techniques with the graphing calculator. Geometric models, through their corresponding area formulas, are constructed, tested, and analyzed graphically to fit specified problem conditions. These specialized versions are then synthesized into generalizations that determine a polygon containing integral sides with a given perimeter and area.     

Visibility and parallelotopes in projective space

It is shown that if is a finite set of points in an ordered d-dimensional projective space, d2 and if all the hyperplanes spanned by points of are considered, then every such a hyperplane is visible from at most 2^d distinct points of ; if a hyperplane bounds 2^d distinct residences, then it contains exactly d points of . These results have been proved previously for d=2 and d=3.This paper is a revised version of results presented at the Conference on Geometry held at the University of Haifa (Israel), March. 10–13 (1975), [6].