Visibility Queries and Maintenance in Simple Polygons

Abstract. In this paper we explore some novel aspects of visibility for stationary and moving points inside a simple polygon P . We provide a mechanism for expressing the visibility polygon from a point as the disjoint union of logarithmically many canonical pieces using a quadratic-space data structure. This allows us to report visibility polygons in time proportional to their size, but without the cubic space overhead of earlier methods. The same canonical decomposition can be used to determine visibility within a frustum, or to compute various attributes of the visibility polygon efficiently. By exploring the connection between visibility polygons and shortest-path trees, we obtain a kinetic algorithm that can track the visibility polygon as the viewpoint moves along polygonal paths inside P , at a polylogarithmic cost per combinatorial change in the visibility or in the flight plan of the point. The combination of the static and kinetic algorithms leads to a new static algorithm in which we can trade off space for increased overhead in the query time. As another application, we obtain an algorithm which computes the weak visibility polygon from a query segment inside P in output-sensitive time.     

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.     

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.     

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.     

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

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.     

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.     

Flipturning Polygons

   Abstract. A flipturn transforms a nonconvex simple polygon into another simple polygon by rotating a concavity 180° around the midpoint of its bounding convex hull edge. Joss and Shannon proved in 1973 that a sequence of flipturns eventually transforms any simple polygon into a convex polygon. This paper describes several new results about such flipturn sequences. We show that any orthogonal polygon is convexified after at most n-5 arbitrary flipturns, or at most

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.     

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.