Minimal containment under homothetics: a simple cutting plane approach

Minimal containment problems arise in a variety of applications, such as shape fitting and packing problems, data clustering, pattern recognition, or medical surgery. Typical examples are the smallest enclosing ball, cylinder, slab, box, or ellipsoid of a given set of points.     

Exploring Polygon Rings

Some topics in mathematics are unique because they can be explored by learners from the early grades through the advanced grades. One such topic is polygon rings. As suggested in the Curriculum and Evaluation Standards for School Mathematics ( National Council of Teachers of Mathematics. 1989 ), students can learn mathematics by actively engaging in the activities outlined in this article. The activities integrate problem solving, reasoning, and communication, and they offer a fascinating look at the beauty of the structure of mathematics.     

Untangling a Polygon

   Abstract. The following problem was raised by M. Watanabe. Let P be a self-intersecting closed polygon with n vertices in general position. How manys steps does it take to untangle P , i.e., to turn it into a simple polygon, if in each step we can arbitrarily relocate one of its vertices. It is shown that in some cases one has to move all but at most O((n log n) ^2/3 ) vertices. On the other hand, every polygon P can be untangled in at most

Wavelet subspaces invariant under groups of translation operators

We study the action of translation operators on wavelet subspaces. This action gives rise to an equivalence relation on the set of all wavelets. We show by explicit construction that each of the associated equivalence classes is non-empty.     

On the Newton Polygon

Partially supported by NSF grant DMS 900-2876.     

Efficient Regular Polygon Dissections

We study the minimum number g(m,n) (respectively, p(m,n)) of pieces needed to dissect a regular m-gon into a regular n-gon of the same area using glass-cuts (respectively, polygonal cuts). First we study regular polygon-square dissections and show that n/2 -2 g(4,n) (n/2) + o(n) and n/4 g(n,4) (n/2) + o(n) hold for sufficiently large n. We also consider polygonal cuts, i.e., the minimum number p(4,n) of pieces needed to dissect a square into a regular n-gon of the same area using polygonal cuts and show that n/4 p(4,n) (n/2) + o(n) holds for sufficiently large n. We also consider regular polygon-polygon dissections and obtain similar bounds for g(m,n) and p(m,n).     

Polygon Recognition and Symmetry Detection

We introduce an approach based on moving frames for polygon recognition and symmetry detection. We present detailed algorithms for the recognition of polygons in R² modulo the special Euclidean, Euclidean, equi-affine, skewed-affine, and similarity Lie groups. We also solve the case of polygons in the Poincar\'e half-plane under the action of SL(2) and explain a method applicable to Lie group actions in general. The time complexity of our algorithms is linear in the number of vertices and they are noise resistant. The signatures used allow the detection of partial, as well as approximate, equivalences.     

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.     

On circle containment orders

A partially ordered set is called acircle containment order provided one can assign to each element of the poset a circle in the plane so thatxy iff the circle assigned tox is contained in the circle assigned toy. It has been conjectured that every finite three-dimensional partially ordered set is a circle containment order. We show that the infinite three dimensional posetZ ³ isnot a circle containment order.Research supported in part by the Office of Naval Research, contract number N00014-85-K0622.Research supported in part by National Science Foundation, grant number DMS-8403646.     

The polygonal containment model

The polygonal containment problem is to position two structures of convex forms under rigid motion mechanics such that the forms of one structure are completely contained within the elements of the associated structure. In this note, the polygonal containment problem is formalized in terms of a generalized containment model and solved as a constrained nonlinear program.     

Covering a Convex Polygon by Triangles

According to a theorem of A. V. Bogomolnaya, F. L. Nazarov and S. E. Rukshin, if n points are given inside a convex n-gon, then the points and the sides of the polygon can be numbered from 1 to n so that the triangles spanned by the ith point and the ith side(i=1....,n ) cover the polygon. In this paper, we prove that the same can be done without assuming that the given points are inside the convex n-gon. We also show that in the general case at least [(n/3)] mutually nonoverlapping triangles can be constructed in the same manner.     

Cross-Ratios and Angles Determine a Polygon

We prove that a unique simple polygon is determined, up to similarity, by the interior angles at its vertices and the cross-ratios of diagonals of any given triangulation. (The cross-ratio of a diagonal is the product of the ratio of edge lengths for the two adjacent triangles.) This establishes a conjecture of Driscoll and Vavasis, and shows the correctness of a key step of their algorithm for computing Schwarz—Christoffel transformations mapping a disk to a polygon. Received April 10, 1998, and in revised form March 24, 1999.     

凸多边形切割方法

本文讨论了二维平面上给定区域内的凸多边形切割问题 .按“顶点度数”该问题可以分为两种类型 .在两种类型下并给出了凸多边形的简单切割方法 .     

线性多边形链的彩虹路连通性(英文)

假定G是一个非平凡的连通图,对G的边全部着上颜色,相邻的边可以着相同的颜色.用数字表示颜色,并假定c:E(G)→{1,2,…,k,k∈N}是G的一种着色方式.G中的一条道路P称为是一条彩虹路,如果P所经过的边的颜色各不相同.如果图G的任意两点间都有一条彩虹路,则称G是彩虹路连通的.使得图G为彩虹路连通所使用的最少颜色数k称为G的彩虹路连通数.本文计算了线性多边形链图的彩虹路2～连通度和线性偶数边多边形链图的彩虹路连通数.     

Quadrilaterizing an Orthogonal Polygon in Parallel

We consider the problem of quadrilaterizing an orthogonal polygon P, that is to decompose P into nonoverlapping convex quadrangles without adding new vertices. In this paper we present a CREW-algorithm for this problem which runs in O(log N) time using Θ(N/log N) processors if the rectangle decomposition of P is given, and Θ(N) processors if not. Furthermore we will show that the latter result is optimal if the polygon is allowed to contain holes.