Narrow Results

We propose time-optimal algorithms for a number of convex polygon problems on meshes with multiple broadcasting. Specifically, we show that on a mesh with multiple broadcasting of size n × n, the task of deciding whether an n-gon is convex, deciding whether two convex n-gons edge-intersect, deciding whether one convex n-gon lies in the interior of another, as well as variants of the tasks of computing the intersection and union of two convex n-gons can be accomplished in Θ(log n) time. We also show that detecting whether two convex n-gons are separable takes O(1) time.

Given a set $S$ of $n$ points in the plane, how many universal guards are sometimes necessary and always sufficient to guard any simple polygon with vertex set $S$? We call this problem a Universal Guard Problem and provide a spectrum of results. We give upper and lower bounds on the number of universal guards that are always sufficient to guard all polygons having a given set of $n$ vertices, or to guard all polygons in a given set of $k$ polygons on an $n$-point vertex set. Our upper bound proofs include algorithms to construct universal guard sets of the respective cardinalities.

We study the shortest $k$-violation path problem in a simple polygon. Let $P$ be a simple polygon in ${ℝ}^2$ with $n$ vertices and let $s,t$ be a pair of points in $P$. Let $int(P)$ represent the interior of $P$. Let $\tilde{P}={ℝ}^2\backslash int(P)$ represent the exterior of $P$. For an integer $k\ge 0$, the shortest $k$-violation path problem in $P$ is the problem of computing the shortest path from $s$ to $t$ in $P$, such that at most $k$ path segments are allowed to be in $\tilde{P}$. The subpaths of a $k$-violation path are not allowed to bend in $\tilde{P}$. For any $k$, we present a $(1+2𝜖)$ factor approximation algorithm for the problem that runs in $O(n^2{\sigma }^{2}klog{n}^2{\sigma }^2+n^2{\sigma }^{2}k)$ time. Here $\sigma =O({log}_{\delta }(\frac{L}{r}))$ and $\delta$, $L$, $r$ are geometric parameters.

In this paper, we consider two distinct problems related to complexity aspects of the visibility graphs of simple polygons. Recognizing visibility graphs is a long-standing open problem. It is not even known whether visibility graph recognition is in NP. That visibility graph recognition is in NP would be established if we could demonstrate that any n vertex visibility graph is realized by a polygon which can be drawn on an exponentially-sized grid. This motivates a study of the area requirements for realizing visibility graphs. In this paper, we prove:

• Θ(n³) area is necessary and sufficient to realize the complete visibility graph K_n.

• There exist visibility graphs which require exponential area to realize.

• Any maximal outerplanar graph of diameter d can be realized in O(d² · 2^d) area, which can be as small as O(n log² n) for a balanced mop. Linear maximal outer-planar graphs can be realized in O(n⁸) area.

The second part of this paper considers the complexity of specific optimization problems on visibility graphs. Given a polygon P, we show that finding a maximum independent set, minimum vertex cover, or maximum dominating set in the visibility graph of P are all NP-complete. Further we show that for polygons P₁ and P₂, the problem of testing if they have isomorphic visibility graphs is isomorphism-complete. These problems remain hard when given the visibility graphs as input.

Let shape P be any simply-connected set in the plane, bounded by a Jordan curve, that is not a circular disk. We say that a set of points I on the boundary of P immobilize the shape if any rigid motion of P in the plane causes at least one point of I to penetrate the interior of P. We prove that four points always suffice to immobilize any shape. For a large class of shapes, which includes polygons without parallel edges, three points are sufficient to immobilize. An O(n log n) algorithm is given that finds a set 3 points that immobilize a given polygon without parallel edges. The algorithm becomes linear for convex polygons. Some results are generalized for d-dimensional polytopes, where 2d points are always sufficient and sometimes necessary to immobilize.

This work is motivated by a paper of Huh and Oh, in which the authors prove that the minimum number of sticks required to form a knot in ℤ³ is 12. In this article the authors prove that the stick number in the simple hexagonal lattice is 11. Moreover, the stick number of the trefoil in the simple hexagonal lattice is 11.

In this paper, we consider knotting of Gaussian random polygons in 3-space. A Gaussian random polygon is a piecewise linear circle with n edges in which the length of the edges follows a Gaussian distribution. We prove a continuum version of Kesten's Pattern Theorem for these polygons, and use this to prove that the probability that a Gaussian random polygon of n edges in 3-space is knotted tends to one exponentially rapidly as n tends to infinity. We study the properties of Gaussian random knots, and prove that the entanglement complexity of Gaussian random knots gets arbitrarily large as n tends to infinity. We also prove that almost all Gaussian random knots are chiral.

The Greeks understood, around 350 B.C., how to construct, with Euclidean tools, regular N-gons for N = 2^cN₀, where N₀ = 1, 3, 5 or 15. Two thousand years later, Gauss proved that a Euclidean construction of a regular N-gon is possible if and only if N = 2^c × (product of distinct Fermat primes).

Here we are content to constuct arbitrarily close approximations to regular polygons. Our constructions lead to some interesting number theory involving the Euler totient function. For a given odd number b, and a given odd number , we construct a numerical array, called a symbol and describe an explicit procedure based on the symbol for constructing a regular star -gon.

We can combine the symbols for a given b to produce a complete symbol where each constituent symbol is called a coach. We present two theorems, the Quasi-Order Theorem and the Coach Theorem, which show how the numbers appearing in the symbol (and hence the steps in our constructions) are governed by the values of Φ(b) and the quasi-order of b mod 2. We then generalize the results to any arbitrary base.

In this paper, we consider knotting of Gaussian random polygons in 3-space . A Gaussian random polygon is a piecewise linear circle with n edges in which the length of the edges follows a Gaussian distribution. We prove a continuum version of Kesten's Pattern Theorem for these polygons, and use this to prove that the probability that a Gaussian random polygon of n edges in 3-space is knotted tends to one exponentially rapidly as n tends to infinity . We study the properties of Gaussian random knots, and prove that the entanglement complexity of Gaussian random knots gets arbitrarily large as n tends to infinity. We also prove that almost all Gaussian random knots are chiral.