Polygon exploration with time-discrete vision

With the advent of autonomous robots with two- and three-dimensional scanning capabilities, classical visibility-based exploration methods from computational geometry have gained in practical importance. However, real-life laser scanning of useful accuracy does not allow the robot to scan continuously while in motion; instead, it has to stop each time it surveys its environment. This requirement was studied by Fekete, Klein and Nüchter for the subproblem of looking around a corner, but until now has not been considered in an online setting for whole polygonal regions.We give the first algorithmic results for this important optimization problem that combines stationary art gallery-type aspects with watchman-type issues in an online scenario: We demonstrate that even for orthoconvex polygons, a competitive strategy can be achieved only for limited aspect ratio A (the ratio of the maximum and minimum edge length of the polygon), i.e., for a given lower bound on the size of an edge; we give a matching upper bound by providing an O(logA)-competitive strategy for simple rectilinear polygons, using the assumption that each edge of the polygon has to be fully visible from some scan point.     

Covering grids and orthogonal polygons with periscope guards

The problem of finding minimum guard covers is NP-hard for simple polygons and open for simple orthogonal polygons. Alternative definitions of visibility have been considered for orthogonal polygons. In this paper we try to determine the complexity of finding guard covers in orthogonal polygons by considering periscope visibility. Under periscope visibility, two points in an orthogonal polygon are visible if there is an orthogonal path with at most one bend that connects them without intersecting the exterior of the polygon. We show that finding minimum periscope guard (as well as k-periscope and s-guard) covers is NP-hard for 3-d grids. We present an O(n³) algorithm for finding minimum periscope guard covers for simple grids and discuss how to extend the algorithm to obtain minimum k-periscope guard covers. We show that this algorithm can be applied to obtain minimum periscope guard covers for a class of simple orthogonal polygon in O(n³).     

Tight bounds for the number of edge guards for spiral polygons

In this paper we give tight lower and upper bounds for the number of edge guards required for covering spiral polygons. We have proved that [(n + 2)/5]edge guards are necessary and sufficient to cover a spiral polygon. It has been shown by Aggarwal [2] that [(n + 2)/5]diagonal guards are necessary and sufficient to cover a spiral polygon. Edge guards are more restrictive than diagonal guards. Hence the previous theorem can be got as a corollary using our theorem. The necessary condition of the edge guard problem for spiral polygons has not been investigated although the diagonal guard problem for the same has been solved [2]. The necessary proof of the edge guard problem follows from the necessary condition of the diagonal guard problem but we have given an alternate proof of necessity.     

Finding largest small polygons with GloptiPoly

A small polygon is a convex polygon of unit diameter. We are interested in small polygons which have the largest area for a given number of vertices n. Many instances are already solved in the literature, namely for all odd n, and for n = 4, 6 and 8. Thus, for even n ≥ 10, instances of this problem remain open. Finding those largest small polygons can be formulated as nonconvex quadratic programming problems which can challenge state-of-the-art global optimization algorithms. We show that a recently developed technique for global polynomial optimization, based on a semidefinite programming approach to the generalized problem of moments and implemented in the public-domain Matlab package GloptiPoly, can successfully find largest small polygons for n = 10 and n = 12. Therefore this significantly improves existing results in the domain. When coupled with accurate convex conic solvers, GloptiPoly can provide numerical guarantees of global optimality, as well as rigorous guarantees relying on interval arithmetic.     

A universal result for consecutive random subdivision of polygons

We consider consecutive random subdivision of polygons described as follows. Given an initial convex polygon with edges, we choose a point at random on each edge, such that the proportions in which these points divide edges are i.i.d. copies of some random variable ξ. These new points form a new (smaller) polygon. By repeatedly implementing this procedure we obtain a sequence of random polygons. The aim of this paper is to show that under very mild non‐degenerateness conditions on ξ, the shapes of these polygons eventually become “flat” The convergence rate to flatness is also investigated; in particular, in the case of triangles (d = 3), we show how to calculate the exact value of the rate of convergence, connected to Lyapunov exponents. Using the theory of products of random matrices our paper greatly generalizes the results of [11] which are achieved mostly by using ad hoc methods. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 341–371, 2017     

An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem

The irregular strip packing problem is a combinatorial optimization problem that requires to place a given set of two-dimensional polygons within a rectangular container so that no polygon overlaps with other polygons or protrudes from the container, where each polygon is not necessarily convex. The container has a fixed width, while its length can change so that all polygons are placed in it. The objective is to find a layout of the set of polygons that minimizes the length of the container.We propose an algorithm that separates overlapping polygons based on nonlinear programming, and an algorithm that swaps two polygons in a layout so as to find their new positions in the layout with the least overlap. We incorporate these algorithms as components into an iterated local search algorithm for the overlap minimization problem and then develop an algorithm for the irregular strip packing problem using the iterated local search algorithm. Computational comparisons on representative instances disclose that our algorithm is competitive with other existing algorithms. Moreover, our algorithm updates several best known results.     

Converting triangulations to quadrangulations

We study the problem of converting triangulated domains to quadrangulations, under a variety of constraints. We obtain a variety of characterizations for when a triangulation (of some structure such as a polygon, set of points, line segments or planar subdivision) admits a quadrangulation without the use of Steiner points, or with a bounded number of Steiner points. We also investigate the effect of demanding that the Steiner points be added in the interior or exterior of a triangulated simple polygon and propose efficient algorithms for accomplishing these tasks. For example, we give a linear-time method that quadrangulates a triangulated simple polygon with the minimum number of outer Steiner points required for that triangulation. We show that this minimum can be at most n/3, and that there exist polygons that require this many such Steiner points. We also show that a triangulated simple n-gon may be quadrangulated with at most n/4 Steiner points inside the polygon and at most one outside. This algorithm also allows us to obtain, in linear time, quadrangulations from general triangulated domains (such as triangulations of polygons with holes, a set of points or line segments) with a bounded number of Steiner points.     

Simple agents learn to find their way: An introduction on mapping polygons

This paper gives an introduction to the problem of mapping simple polygons with autonomous agents. We focus on minimalistic agents that move from vertex to vertex along straight lines inside a polygon, using their sensors to gather local data at each vertex. Our attention revolves around the question whether a given configuration of sensors and movement capabilities of the agents allows them to capture enough data in order to draw conclusions regarding the global layout of the polygon.In particular, we study the problem of reconstructing the visibility graph of a simple polygon by an agent moving either inside or on the boundary of the polygon. Our aim is to provide insight about the algorithmic challenges faced by an agent trying to map a polygon. We present an overview of techniques for solving this problem with agents that are equipped with simple sensorial capabilities. We illustrate these techniques on examples with sensors that measure angles between lines of sight or identify the previous location. We also give an overview over related problems in combinatorial geometry as well as graph exploration.     

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.     

Complete and robust no-fit polygon generation for the irregular stock cutting problem

The no-fit polygon is a construct that can be used between pairs of shapes for fast and efficient handling of geometry within irregular two-dimensional stock cutting problems. Previously, the no-fit polygon (NFP) has not been widely applied because of the perception that it is difficult to implement and because of the lack of generic approaches that can cope with all problem cases without specific case-by-case handling. This paper introduces a robust orbital method for the creation of no-fit polygons which does not suffer from the typical problem cases found in the other approaches from the literature. Furthermore, the algorithm only involves two simple geometric stages so it is easily understood and implemented. We demonstrate how the approach handles known degenerate cases such as holes, interlocking concavities and jigsaw type pieces and we give generation times for 32 irregular packing benchmark problems from the literature, including real world datasets, to allow further comparison with existing and future approaches.     

On convexification of polygons by pops

Given a polygon P in the plane, a pop operation is the reflection of a vertex with respect to the line through its adjacent vertices. We define a family of alternating polygons, and show that any polygon from this family cannot be convexified by pop operations. This family contains simple as well as non-simple (i.e., self-intersecting) polygons, as desired. We thereby answer in the negative an open problem posed by Demaine and O’Rourke (2007) [9, Open Problem 5.3].     

Polygon vertex extremality and decomposition of polygons

In this paper, we show that if we decompose a polygon into two smaller polygons, then by comparing the number of extremal vertices in the original polygon versus the sum of the two smaller polygons, we can gain at most two globally extremal vertices in the smaller polygons, as well as at most two locally extremal vertices. We then will derive two discrete Four-Vertex Theorems from our results.     

On the Structure of Multiple Translational Tilings by Polygonal Regions

We consider polygons with the following ``pairing property': for each edge of the polygon there is precisely one other edge parallel to it. We study the problem of when such a polygon K tiles multiply the plane when translated at the locations Λ , where Λ is a multiset in the plane. The pairing property of K makes this question particularly amenable to Fourier analysis. As a first application of our approach we establish a necessary and sufficient condition for K to tile with a given lattice Λ . (This was first found by Bolle for the case of convex polygons—notice that all convex polygons that tile, necessarily have the pairing property and, therefore, our theorems apply to them.) Our main result is a proof that a large class of such polygons tile multiply only quasi-periodically, which for us means that Λ must be a finite union of translated two-dimensional lattices in the plane. For the particular case of convex polygons we show that all convex polygons which are not parallelograms tile multiply only quasi-periodically, if at all. Received February 24, 1999, and in revised form August 26, 1999, and October 9, 1999.     

Edge guards for the fortress problem

The fortress problem is one of determining a set of guards to cover the exterior of a simple polygon. O'Rourke and Wood [cited in 7] showed that vertex guards are sometimes necessary and always sufficient for an -vertex polygon. In this paper, we solve the same problem for edge guards. Tight bounds of and edge guards are obtained for general and rectilinear polygons, respectively. Received 19 June 1999; in revised form 23 March 2000.     

A One-Parametric Method for Determining Parameters in the Schwarz–Christoffel Integral

We propose a method for determining parameters in the Schwarz–Christoffel integral. The desired mapping embeds into a one-parametric family of conformal mappings of the upper half-plane onto the family of polygons which was obtained by shifting one or several vertices of some initial polygon with angle preservation. We consider the case when the family of polygons and the initial polygon have the same number of vertices; the case when the family of polygons has two mobile vertices coinciding at the initial moment and not coinciding with other vertices; and the other case that the family of polygons is a polygon with mobile cut. The problem of finding the parameters of a family of mappings is reduced to integrating some system of ordinary differential equations.

     

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.     

An efficient algorithm for the regular W<Subscript>1</Subscript> packing of polygons in the infinite plane

This paper describes a new algorithm, PLANEPACK, which determines an optimal or near optimal solution for the W₁ packing of identical shapes in the infinite plane. Restricted to polygons for computational convenience, it is based on the no-fit polygon/configuration space obstacle approach. The algorithm was tested on a modest set of fourteen polygons (thirteen non-interlocking and one interlocking) and yielded a feasible solution for each. The solutions were optimal for four of the non-interlocking polygons and near optimal for the other nine. As expected though, the solution for the one interlocking polygon was sub-optimal and enhancements to the algorithm would be required for such cases.     

A note on the approximation of Dirichlet boundary control problems for the wave equation on curved domains

We consider an exact boundary control problem for the wave equation with given initial and terminal data and Dirichlet boundary control. The aim is to steer the state of the system that is defined on a given domain to a position of rest in finite time. The optimal control that is obtained as the solution of the problem depends on the data that define the problem, in particular on the domain. Often for the numerical solution of the control problem, this given domain is replaced by a polygon. This is the motivation to study the convergence of the optimal controls for the polygon to the optimal controls for the given domain. To study the convergence, the values of the optimal controls that are defined on the boundaries of the approximating polygons are mapped in the normal directions of the polygon to control functions defined on the boundary of the original domain. This map has already been used by Bramble and King, Deckelnick, Guenther and Hinze and by Casas and Sokolowski. Using this map, we can show the strong convergence of the transformed controls as the polygons approach the given domain. An essential tool to obtain the convergence is a regularization term in the objective functions to increase the regularity of the state.     

Decomposing a simple polygon into pseudo-triangles and convex polygons

In this paper we consider the problem of decomposing a simple polygon into subpolygons that exclusively use vertices of the given polygon. We allow two types of subpolygons: pseudo-triangles and convex polygons. We call the resulting decomposition PT-convex. We are interested in minimum decompositions, i.e., in decomposing the input polygon into the least number of subpolygons. Allowing subpolygons of one of two types has the potential to reduce the complexity of the resulting decomposition considerably.The problem of decomposing a simple polygon into the least number of convex polygons has been considered. We extend a dynamic-programming algorithm of Keil and Snoeyink for that problem to the case that both convex polygons and pseudo-triangles are allowed. Our algorithm determines such a decomposition in O(n³) time and space, where n is the number of the vertices of the polygon.