The perimeter of rounded convex planar sets

A convex set is inscribed into a rectangle with sides a and 1/a so that the convex set has points on all four sides of the rectangle. By “rounding” we mean the composition of two orthogonal linear transformations parallel to the edges of the rectangle, which makes a unit square out of the rectangle. The transformation is also applied to the convex set, which now has the same area, and is inscribed into a square. One would expect this transformation to decrease the perimeter of the convex set as well. Interestingly, this is not always the case. For each a we determine the largest and smallest possible increase of the perimeter.      

The Cruciform Crack Problem and Sigmoidal Transformations

A sigmoidal transformation is an S-shaped one-to-one mapping of a compact interval onto itself. Various sigmoidal transformations are discussed, some of which are used to find approximate solutions of an integral equation, with a fixed singularity, arising from a problem in elasticity. In particular it is shown that, in this context, a sigmoidal transformation due to Sidi gives the best results. © 1997 by B.G. Teubner Stuttgart-John Wiley & Sons, Ltd.     

Covering an Annulus by Strips

Take a unit square and turn it into an annulus by cutting a parallel square hole in it. We prove that if the square hole has edge length $1 - 1/ \sqrt2 \approx 0.29$ and a finite number of strips cover the annulus, then after appropriate rearrangement the same strips can cover the unit square as well.     

Analytic properties of Rényi’s invariant density

Under certain conditions a many-to-one transformation of the unit interval onto itself possesses a finite invariant ergodic measure equivalent to Lebesgue measure. The purpose of this paper is to investigate these conditions and to show how differentiable and analytic properties of the invariant density are inherited from the original transformation.     

Algorithms for Unconstrained Two-Dimensional Guillotine Cutting

In this paper we consider the unconstrained, two-dimensional, guillotine cutting problem. This is the problem that occurs in the cutting of a number of rectangular pieces from a single large rectangle, so as to maximize the value of the pieces cut, where any cuts that are made are restricted to be guillotine cuts.We consider both the staged version of the problem (where the cutting is performed in a number of distinct stages) and the general (non-staged) version of the problem.A number of algorithms, both heuristic and optimal, based upon dynamic programming are presented. Computational results are given for large problems.     

A tabu search algorithm for a two-dimensional non-guillotine cutting problem

In this paper we study a two-dimensional non-guillotine cutting problem, the problem of cutting rectangular pieces from a large stock rectangle so as to maximize the total value of the pieces cut. The problem has many industrial applications whenever small pieces have to be cut from or packed into a large stock sheet. We propose a tabu search algorithm. Several moves based on reducing and inserting blocks of pieces have been defined. Intensification and diversification procedures, based on long-term memory, have been included. The computational results on large sets of test instances show that the algorithm is very efficient for a wide range of packing and cutting problems.     

On finite limit sets for transformations on the unit interval

An infinite sequence of finite or denumerable limit sets is found for a class of many-to-one transformations of the unit interval into itself. Examples of four different types are studied in some detail; tables of numerical results are included. The limit sets are characterized by certain patterns; an algorithm for their generation is described and established. The structure and order of occurrence of these patterns is universal for the class.     

On the invertibility of mappings arising in 2D grid generation problems

Summary. In adapting a grid for a Computational Fluid Dynamics problem one uses a mapping from the unit square onto itself that is the solution of an elliptic partial differential equation with rapidly varying coefficients. For a regular discretization this mapping has to be invertible. We will show that such result holds for general elliptic operators (in two dimensions). The Carleman-Hartman-Wintner Theorem will be fundamental in our proof. We will also explain why such a general result cannot be expected to hold for the (three-dimensional) cube. Received March 1, 1994 / Revised version received March 8, 1995     

Gedämpfte zahlentheoretische Transformationen

Generalizing earlier work ofJ. Galambos and the present author a model of a class of transformations mapping the unit interval into itself is proposed. This class contains the classical series expansions of Sylvester and Engel, the algorithm of Pierce and a lot of their genralizations. The main result is an ergodic theorem: the space mean of a certain sequence equals the time mean almost every-where.     

Construction heuristics for two-dimensional irregular shape bin packing with guillotine constraints

The paper examines a new problem in the irregular packing literature that has many applications in industry: two-dimensional irregular (convex) bin packing with guillotine constraints. Due to the cutting process of certain materials, cuts are restricted to extend from one edge of the stock-sheet to another, called guillotine cutting. This constraint is common place in glass cutting and is an important constraint in two-dimensional cutting and packing problems. In the literature, various exact and approximate algorithms exist for finding the two dimensional cutting patterns that satisfy the guillotine cutting constraint. However, to the best of our knowledge, all of the algorithms are designed for solving rectangular cutting where cuts are orthogonal with the edges of the stock-sheet. In order to satisfy the guillotine cutting constraint using these approaches, when the pieces are non-rectangular, practitioners implement a two stage approach. First, pieces are enclosed within rectangle shapes and then the rectangles are packed. Clearly, imposing this condition is likely to lead to additional waste. This paper aims to generate guillotine-cutting layouts of irregular shapes using a number of strategies. The investigation compares three two-stage approaches: one approximates pieces by rectangles, the other two approximate pairs of pieces by rectangles using a cluster heuristic or phi-functions for optimal clustering. All three approaches use a competitive algorithm for rectangle bin packing with guillotine constraints. Further, we design and implement a one-stage approach using an adaptive forest search algorithm. Experimental results show the one-stage strategy produces good solutions in less time over the two-stage approach.     

Bounds for Two-Dimensional Cutting

This note considers the problem of cutting rectangular pieces from a single large rectangle so as to maximize the value of the pieces cut. A number of bounds that can be used in any tree search procedure for the problem are derived from a zero-one formulation of the problem. Computational results are presented.     

Cutting and stacking,interval exchanges and geometric models

Every aperiodic measure-preserving transformation can be obtained by a cutting and stacking construction. It follows that all such transformations are infinite interval exchanges. This in turn is used to represent any ergodic measure-preserving flow as aC ^∞-flow on an open 2-manifold. Several additional applications of the basic theorems are also given. Partial support for this work was given by the National Science Foundation under grant number MCS81-07092.     

A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems

This paper presents a greedy randomized adaptive search procedure (GRASP) for the constrained two-dimensional non-guillotine cutting problem, the problem of cutting the rectangular pieces from a large rectangle so as to maximize the value of the pieces cut. We investigate several strategies for the constructive and improvement phases and several choices for critical search parameters. We perform extensive computational experiments with well-known instances previously reported, first to select the best alternatives and then to compare the efficiency of our algorithm with other procedures.     

Interval exchange transformations and some special flows are not mixing

An interval exchange transformation (I.E.T.) is a map of an interval into itself which is one-to-one and continuous except for a finite set of points and preserves Lebesgue measure. We prove that any I.E.T. is not mixing with respect to any Borel invariant measure. The same is true for any special flow constructed by any I.E.T. and any “roof” function of bounded variation. As an application of the last result we deduce that in any polygon with the angles commensurable with π the billiard flow is not mixing on two-dimensional invariant manifolds. The author is partially supported by grant NSF MCS 78-15278.     

A Local Optimization-based Solution to the Rectangle Layout Problem

In this paper we apply a family of heuristics to solve the rectangle layout problem. Our principal technique, however, is a variant of local optimization. This technique, which we call sacrificing, differs from the traditional local optimization algorithm in two respects. Firstly, we relax the monotonicity requirement by permitting intermediate solutions that are not the best seen to date; secondly, we expand the notion of neighbourhood to include families of solution perturbation schemes. We solve a problem by combining these simple transformations into a high-level program with sacrificing our key transformation. We demonstrate the effectiveness of our approach on a number of test cases.     

Transformations of Border Strips and Schur Function Determinants

We introduce the notion of the cutting strip of an outside decomposition of a skew shape, and show that cutting strips are in one-to-one correspondence with outside decompositions for a given skew shape. Outside decompositions are introduced by Hamel and Goulden and are used to give an identity for the skew Schur function that unifies the determinantal expressions for the skew Schur functions including the Jacobi-Trudi determinant, its dual, the Giambelli determinant and the rim ribbon determinant due to Lascoux and Pragacz. Using cutting strips, one obtains a formula for the number of outside decompositions of a given skew shape. Moreover, one can define the basic transformations which we call the twist transformation among cutting strips, and derive a transformation theorem for the determinantal formula of Hamel and Goulden. The special case of the transformation theorem for the Giambelli identity and the rim ribbon identity was obtained by Lascoux and Pragacz. Our transformation theorem also applies to the supersymmetric skew Schur function.     

First-order accurate finite difference schemes for boundary vorticity approximations in curvilinear geometries

In this work we develop first-order accurate, forward finite difference schemes for the first derivative on both a uniform and a non-uniform grid. The schemes are applied to the calculation of vorticity on a solid wall of a curvilinear, two-dimensional channel. The von Mises coordinates are used to transform the governing equations, and map the irregular domain onto a rectangular computational domain. Vorticity on the solid boundary is expressed in terms of the first partial derivative of the square of the speed of the flow in the computational domain, and the derived finite difference schemes are used to calculate the vorticity at the computational boundary grid points using combinations of up to five computational domain grid points. This work extends previous work (Awartani et al., 2005) [3] in which higher-order schemes were obtained for the first derivative using up to four computational domain grid points. The aim here is to shed further light onto the use of first-order accurate non-uniform finite difference schemes that are essential when the von Mises transformation is used. Results show that the best schemes are those that use a natural sequence of non-uniform grid points. It is further shown that for non-uniform grid with clustering near the boundary, solution deteriorates with increasing number of grid points used. By contrast, when a uniform grid is used, solution improves with increasing number of grid points used.     

Multichannel type-I intermittency in two models of Rayleigh–Bénard convection

We report on the first observation of transitions to deterministic chaos via type-I intermittency with two channels of re-injection in two equivariant autonomous dynamical systems. First, we consider the standard Lorenz system which is equivariant under the action of the rotation of π around the z-axis. We also consider the same phenomenon in a nine-dimensional model of the Rayleigh–Bénard convection which is equivariant under the action of the Klein four group, of all isometries mapping a rectangle, which is not a square, on itself.     

A near equitable 2-person cake cutting algorithm

Let the cake be represented by the unit interval of reals, with two players having possibly different valuations. We propose a finite algorithm that produces contiguous pieces for both players such that their values differ by at most ?, where ??>?0 is a given small number. Players are not required to reveal their complete value functions, they only have to announce the bisection points of a sequence of intervals. If both utility functions are everywhere positive then the algorithm converges to the unique equitable point.     

論矩陣的一種變換

<正> 在本文中,數域限定為複數域.我們要來研究如下的變換:(1)(它將方陣A變成方陣B),式中P表示任意正則陣,P表示P的元素的共軛救構成的陣.所有的變换(1)顯然成羣.這種變換現在姑稱之為種變換.如果二方陣A與B可由一個種變換變此成彼,我們就說,A與B是對相似的.