Deforming star-shaped polygons in the plane

Given a star-shaped polygon in the euclidean plane and a vertex v of the polygon, the author characterizes all those points w in the plane such that when the vertex v moves to w along a straight line path, while all other vertices of the polygon are fixed, the polygon remains star-shaped. An example is given to show that this characterization fails for the star-shaped polyhedral spheres in the 3-dimensional euclidean space.     

A modified Schwarz–Christoffel mapping for regions with piecewise smooth boundaries

A method where polygon corners in Schwarz–Christoffel mappings are rounded, is used to construct mappings from the upper half-plane to regions bounded by arbitrary piecewise smooth curves. From a given curve, a polygon is constructed by taking tangents to the curve in a number of carefully chosen so-called tangent points. The Schwarz–Christoffel mapping for that polygon is then constructed and modified to round the corners.     

Optimizing a constrained convex polygonal annulus

In this paper we give solutions to several constrained polygon annulus placement problems for offset and scaled polygons, providing new efficient primitive operations for computational metrology and dimensional tolerancing. Given a convex polygon P and a planar point set S, the goal is to find the thinnest annulus region of P containing S. Depending on the application, there are several ways this problem can be constrained. In the variants that we address the size of the polygon defining the inner (respectively, outer) boundary of the annulus is fixed, and the annulus is minimized by minimizing (respectively, maximizing) the outer (respectively, inner) boundary. We also provide solutions to a related known problem: finding the smallest homothetic copy of a polygon containing a set of points. For all of these problems, we solve for the cases where smallest and largest are defined by either the offsetting or scaling of a polygon. We also provide some experimental results from implementations of several competing approaches to a primitive operation important to all the above variants: finding the intersection of n copies of a convex polygon.     

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

Empirical Polygon Simulation and Central Limit Theorems for the Homogenous Poisson Line Process

For the Poisson line process the empirical polygon is defined thanks to ergodicity and laws of large numbers for some characteristics, such as the number of edges, the perimeter, the area, etc... One also has, still thanks to the ergodicity of the Poisson line process, a canonical relation between this empirical polygon and the polygon containing a given point. The aim of this paper is to provide numerical simulations for both methods: in a previous paper (Paroux, Advances in Applied Probability, 30:640–656, 1998) one of the authors proved central limit theorems for some geometrical quantities associated with this empirical Poisson polygon, we provide numerical simulations for this phenomenon which generates billions of polygons at a small computational cost. We also give another direct simulation of the polygon containing the origin, which enables us to give further values for empirical moments of some geometrical quantities than the ones that were known or computed in the litterature. This work was partially supported by the PSMN at ENS-Lyon.     

The Newton Polygon of a Rational Plane Curve

The Newton polygon of the implicit equation of a rational plane curve is explicitly determined by the multiplicities of any of its parametrizations. We give an intersection-theoretical proof of this fact based on a refinement of the Kušnirenko–Bernštein theorem. We apply this result to the determination of the Newton polygon of a curve parameterized by generic Laurent polynomials or by generic rational functions, with explicit genericity conditions. We also show that the variety of rational curves with given Newton polygon is unirational and we compute its dimension. As a consequence, we obtain that any convex lattice polygon with positive area is the Newton polygon of a rational plane curve.     

On the number of guard edges of a polygon

This paper establishes tight bounds on the number of edges of a polygon from which every point in the polygon is visible; we call them guard edges. For a nonstarshaped polygon, there can be at most three guard edges. For a polygon with holes, there may be at most six; three on the outer boundary and three on one of the holes. The results give new insights into the structure of visibility in polygons and shed light on developing an efficient algorithm for finding all guard edges of a polygon with or without holes. This work was partially supported by the Korea Science and Engineering Foundation (Project No. 91-01-01).     

Polygon Posets and the Weak Order of Coxeter Groups

We explore the connection between polygon posets, which is a class of ranked posets with an edge-labeling which satisfies certain polygon properties, and the weak order of Coxeter groups. We show that every polygon poset is isomorphic to a join ideal in the weak order, and for Coxeter groups where no pair of generators have infinite order the converse is also true.The class of polygon posets is seen to include the class of generalized quotients defined by Björner and Wachs, while itself being included in the class of alternative generalized quotients also considered by these authors. By studying polygon posets we are then able to answer an open question about common properties of these two classes.     

How Many Diagonal Rectangles Are Needed to Cover an Orthogonal Polygon?

We show that any orthogonal polygon of n vertices can be covered with at most ``diagonal rectangles' where ω=1 (n=8,12,16) and ω=0 (otherwise). An orthogonal polygon is a polygon whose edges are horizontal or vertical. A diagonal rectangle (of an orthogonal polygon) is a rectangle whose opposite corners are vertices of the orthogonal polygon. The result is sharp and settles a question of Mamoru Watanabe [11]. Received July 25, 1999, and in revised form March 1, 2000. Online publication May 16, 2000.     

Convex drawings of graphs with non-convex boundary constraints

In this paper, we study a new problem of convex drawing of planar graphs with non-convex boundary constraints, and call a drawing in which every inner-facial cycle is drawn as a convex polygon an inner-convex drawing. It is proved that every triconnected plane graph with the boundary fixed with a star-shaped polygon whose kernel has a positive area admits an inner-convex drawing. We also prove that every four-connected plane graph whose boundary is fixed with a crown-shaped polygon admits an inner-convex drawing. We present linear time algorithms to construct inner-convex drawings for both cases.     

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.     

A polygon is determined by its angles

We study the problem of reconstructing a simple polygon from angles measured at the vertices of the polygon. We assume that at each vertex v a sensing device returns a list of angles α₁,α₂,…, where αi is the angle between the i-th and the (i+1)-th vertices visible to v in counterclockwise (ccw) order starting with the ccw neighbor of v along the boundary. We prove that the angle measurements at all vertices of a simple polygon together with the order of the vertices along the boundary uniquely determine the polygon (up to similarity). In addition, we give an algorithm for reconstructing the polygon from this information in polynomial time.     

Offset-polygon annulus placement problems

An offset-polygon annulus region is defined in terms of a polygon P and a distance δ > 0 (offset of P). In this paper we solve several containment problems for polygon annulus regions with respect to an input point set. Optimization criteria include both maximizing the number of points contained in a fixed size annulus and minimizing the size of the annulus needed to contain all points. We address the following variants of the problem: placement of an annulus of a convex polygon as well as of a simple polygon; placement by translation only, or by translation and rotation; off-line and on-line versions of the corresponding decision problems; and decision as well as optimization versions of the problems. We present efficient algorithms in each case.     

Twisted exponential sums of polynomials in one variable

The twisted T-adic exponential sums associated to a polynomial in one variable are studied. An explicit arithmetic polygon in terms of the highest two exponents of the polynomial is proved to be a lower bound of the Newton polygon of the C-function of the twisted T-adic exponential sums. This bound gives lower bounds for the Newton polygon of the L-function of twisted p-power order exponential sums.     

The orthogonal convex skull problem

We give a combinatorial definition of the notion of a simple orthogonal polygon beingk-concave, wherek is a nonnegative integer. (A polygon is orthogonal if its edges are only horizontal or vertical.) Under this definition an orthogonal polygon which is 0-concave is convex, that is, it is a rectangle, and one that is 1-concave is orthoconvex in the usual sense, and vice versa. Then we consider the problem of computing an orthoconvex orthogonal polygon of maximal area contained in a simple orthogonal polygon. This is the orthogonal version of the potato peeling problem. AnO(n ²) algorithm is presented, which is a substantial improvement over theO(n ⁷) time algorithm for the general problem.The work of the first author was supported under a Natural Sciences and Engineering Research Council of Canada Grant No. A-5692 and the work of the second author was partially supported by NSF Grants Nos. DCR-84-01898 and DCR-84-01633.     

A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk

We propose a very simple ray-shooting algorithm, whose only data structure is a triangulation. The query algorithm, after locating the triangle containing the origin of the ray, walks along the ray, advancing from one triangle to a neighboring one until the polygon boundary is reached. The key result of the paper is a Steiner triangulation of a simple polygon with the property that a ray can intersect at most O(log n) triangles before reaching the polygon boundary. We are able to compute such a triangulation in linear sequential time, or in O(log n) parallel time using O(n/log n) processors. This gives a simple, yet optimal, ray-shooting algorithm for a simple polygon. Using a well-known technique, we can extend our triangulation procedure to a multiconnected polygon with k components and n vertices, so that a ray intersects at most O(√k log n) triangles.     

Minimum-Area ellipse containing a finite set of points. II

We continue the investigation of the problem of construction of a minimum-area ellipse for a given convex polygon (this problem is solved for a rectangle and a trapezoid). For an arbitrary polygon, we prove that, in the case where the boundary of the minimum-area ellipse has exactly four or five common points with the polygon, this ellipse is the minimum-area ellipse for the quadrangles and pentagons formed by these common points. Translated from Ukrainskii Matematicheskii Zhurnal, Vol.50, No.8, pp. 1098–1105, August, 1998.     

n-bathycenters

Does there exist a polygon with the property that for a suitable point p in the plane every ray with endpoint p intersects the polygon in exactly n connected components? Does there exist a polygon with the property that there are two such points, or three, or a segment of such points? For polygon P call a point p with the property that every ray from p intersects P in exactly n connected components n-isobathic with respect to P. Define the n-bathycenter of a polygon P as the set of all points p that are n-isobathic with respect to P. Further define a set S to be an n-bathycenter if there exists a polygon P of which S is the n-bathycenter. This paper deals with the characterization of 2- and 3-bathycenters, together with some results on the general case.     

Polygon containment under translation

The polygon containment problem is the problem of deciding whether a polygon P can be translated to fit inside another polygon P'. We present algorithms for two cases of the polygon containment problem: when both P and P' are rectilinearly convex, and when P is convex and P' is arbitrary. In both cases the algorithms run in time O(n²logn), where n is the sum of the number of bounding edges of the two polygons. Applications to an inspection problem and a stock-cutting problem are discussed, as is the containment problem when both P and P' are nonconvex.     

The pentagram map and Y-patterns

The pentagram map, introduced by R. Schwartz, is defined by the following construction: given a polygon as input, draw all of its “shortest” diagonals, and output the smaller polygon which they cut out. We employ the machinery of cluster algebras to obtain explicit formulas for the iterates of the pentagram map.