Computing Cartograms with Optimal Complexity

In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons, while edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight. The complexity of a cartogram is determined by the maximum number of corners (or sides) required for any polygon. In a series of papers the polygonal complexity of such representations for maximal planar graphs has been reduced from the initial 40 to 34, then to 12 and very recently to the currently best known 10. Here we describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity as 8-sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine it into an area-universal rectangular layout in linear time. The exact cartogram can be computed from the area-universal layout with numerical iteration, or can be approximated with a hill-climbing heuristic. We also describe an alternative construction of cartograms for Hamiltonian maximal planar graphs, which allows us to directly compute the cartograms in linear time. Moreover, we prove that even for Hamiltonian graphs 8-sided rectilinear polygons are necessary, by constructing a non-trivial lower bound example. The complexity of the cartograms can be reduced to 6 if the Hamiltonian path has the extra property that it is one-legged, as in outer-planar graphs. Thus, we have optimal representations (in terms of both polygonal complexity and running time) for Hamiltonian maximal planar and maximal outer-planar graphs. Finally we address the problem of constructing small-complexity cartograms for 4-connected graphs (which are Hamiltonian). We first disprove a conjecture, posed by two set of authors, that any 4-connected maximal planar graph has a one-legged Hamiltonian cycle, thereby invalidating an attempt to achieve a polygonal complexity 6 in cartograms for this graph class. We also prove that it is NP-hard to decide whether a given 4-connected plane graph admits a cartogram with respect to a given weight function.     

On rectilinear duals for vertex-weighted plane graphs

Let G=(V,E) be a plane triangulated graph where each vertex is assigned a positive weight. A rectilinear dual of G is a partition of a rectangle into |V| simple rectilinear regions, one for each vertex, such that two regions are adjacent if and only if the corresponding vertices are connected by an edge in E. A rectilinear dual is called a cartogram if the area of each region is equal to the weight of the corresponding vertex. We show that every vertex-weighted plane triangulated graph G admits a cartogram of constant complexity, that is, a cartogram where the number of vertices of each region is constant. Furthermore, such a rectilinear cartogram can be constructed in O(nlogn) time where n=|V|.     

A Numerical Method for Conformal Mapping

A method is developed for constructing the conformal map ofa distorted region onto a rectangle. A discrete Fourier transformis used to map the boundary of the region onto the boundaryof the rectangle; the resulting equations may be solved usinga fast Fourier transform algorithm. The map for internal pointsmay then be constructed using a standard Laplace equation solver.The method is computationally competitive, and is applicableto field problems, for instance in fluid mechanics.     

Cutting ellipses from area-minimizing rectangles

A set of ellipses, with given semi-major and semi-minor axes, is to be cut from a rectangular design plate, while minimizing the area of the design rectangle. The design plate is subject to lower and upper bounds of its widths and lengths; the ellipses are free of any orientation restrictions. We present new mathematical programming formulations for this ellipse cutting problem. The key idea in the developed non-convex nonlinear programming models is to use separating hyperlines to ensure the ellipses do not overlap with each other. For small number of ellipses we compute feasible points which are globally optimal subject to the finite arithmetic of the global solvers at hand. However, for more than 14 ellipses none of the local or global NLP solvers available in GAMS can even compute a feasible point. Therefore, we develop polylithic approaches, in which the ellipses are added sequentially in a strip-packing fashion to the rectangle restricted in width, but unrestricted in length. The rectangle’s area is minimized in each step in a greedy fashion. The sequence in which we add the ellipses is random; this adds some GRASP flavor to our approach. The polylithic algorithms allow us to compute good, near optimal solutions for up to 100 ellipses.     

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.     

Bivariate spline interpolation at grid points

Summary. We describe algorithms for constructing point sets at which interpolation by spaces of bivariate splines of arbitrary degree and smoothness is possible. The splines are defined on rectangular partitions adding one or two diagonals to each rectangle. The interpolation sets are selected in such a way that the grid points of the partition are contained in these sets, and no large linear systems have to be solved. Our method is to generate a net of line segments and to choose point sets in these segments which satisfy the Schoenberg-Whitney condition for certain univariate spline spaces such that a principle of degree reduction can be applied. In order to include the grid points in the interpolation sets, we give a sufficient Schoenberg-Whitney type condition for interpolation by bivariate splines supported in certain cones. This approach is completely different from the known interpolation methods for bivariate splines of degree at most three. Our method is illustrated by some numerical examples. Received October 5, 1992 / Revised version received May 13, 1994     

Local search algorithms for the rectangle packing problem with general spatial costs

We propose local search algorithms for the rectangle packing problem to minimize a general spatial cost associated with the locations of rectangles. The problem is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. Each rectangle has a set of modes, where each mode specifies the width and height of the rectangle and its spatial cost function. The spatial costs are general piecewise linear functions which can be non-convex and discontinuous. Various types of packing problems and scheduling problems can be formulated in this form. To represent a solution of this problem, a pair of permutations of n rectangles is used to determine their horizontal and vertical partial orders, respectively. We show that, under the constraint specified by such a pair of permutations, optimal locations of the rectangles can be efficiently determined by using dynamic programming. The search for finding good pairs of permutations is conducted by local search and metaheuristic algorithms. We report computational results on various implementations using different neighborhoods, and compare their performance. We also compare our algorithms with other existing heuristic algorithms for the rectangle packing problem and scheduling problem. These computational results exhibit good prospects of the proposed algorithms. Key words.rectangle packing – sequence pair – general spatial cost – dynamic programming – metaheuristicsMathematics Subject Classification (1991):20E28, 20G40, 20C20     

Haar wavelets method for solving Poisson equations with jump conditions in irregular domain

In this paper, Haar wavelets method is used to solve Poisson equations in the presence of interfaces where the solution itself may be discontinuous. The interfaces have jump conditions which need to be enforced. It is critical for the approximation of the boundaries of the irregular domain. An irregular domain can be treated by embedding the domain into a rectangular domain and Poisson equation is solved by using Haar wavelets method on the rectangle. Firstly, we demonstrate this method in the case of 1-D region, then we consider the solution of the Poisson equations in the case of 2-D region. The efficiency of the method is demonstrated by some numerical examples.     

Polychromatic colorings of rectangular partitions

A rectangular partition is a partition of a plane rectangle into an arbitrary number of non-overlapping rectangles such that no four rectangles share a corner. In this note, it is proven that every rectangular partition admits a vertex coloring with four colors such that every rectangle, except possibly the outer rectangle, has all four colors on its boundary. This settles a conjecture of Dinitz et al. [Y. Dinitz, M.J. Katz, R. Krakovski, Guarding rectangular partitions, in: Abstracts 23rd Euro. Workshop Comput. Geom., 2007, pp. 30-33]. The proof is short, simple and based on 4-edge-colorability of a specific class of planar graphs.     

An efficient deterministic optimization approach for rectangular packing problems

The rectangular packing problem aims to seek the best way of placing a given set of rectangular pieces within a large rectangle of minimal area. Such a problem is often constructed as a quadratic mixed-integer program. To find the global optimum of a rectangular packing problem, this study transforms the original problem as a mixed-integer linear programming problem by logarithmic transformations and an efficient piecewise linearization approach that uses a number of binary variables and constraints logarithmic in the number of piecewise line segments. The reformulated problem can be solved to obtain an optimal solution within a tolerable error. Numerical examples demonstrate the computational efficiency of the proposed method in globally solving rectangular packing problems.     

The concentration of a wave field at the interface of elastic media

The steady symmetrical oscillations of a transversely non-uniform elastic rectangular region, consisting of three bonded uniformisotropic rectangles, are considered, where the elastic characteristics of the inner rectangle are assumed to be different from those of the external rectangles. Using methods developed previously [1,2], the dependence of the order of the singularity of the stress field at the interface on the combinations of the constants of elasticity of the joined media and on their wave impedances is investigated.     

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.     

Parallel greedy algorithms for packing unequal circles into a strip or a rectangle

Given a finite set of circles of different sizes we study the strip packing problem (SPP) as well as the Knapsack Problem (KP). The SPP asks for a placement of all circles within a rectangular strip of fixed width so that the variable length of the strip is minimized. The KP requires packing of a subset of the circles in a given rectangle so that the wasted area is minimized. To solve these problems some greedy algorithms were developed which enhance the algorithms proposed by Huang et al. (J Oper Res Soc 56:539–548, 2005). Furthermore, the new greedy algorithms were parallelized using a master slave approach. The resulting parallel methods were tested using the instances introduced by Stoyan and Yaskov (Eur J Oper Res 156:590–600, 2004). Additionally, two sets of 128 instances each for the SPP and for the KP were generated and results for these new instances are also reported.     

The knapsack problem with neighbour constraints

We study a constrained version of the knapsack problem in which dependencies between items are given by the adjacencies of a graph. In the 1-neighbour knapsack problem, an item can be selected only if at least one of its neighbours is also selected. In the all-neighbours knapsack problem, an item can be selected only if all its neighbours are also selected.We give approximation algorithms and hardness results when the vertices have both uniform and arbitrary weight and profit functions, and when the dependency graph is directed and undirected.     

货物尺寸相同的2维装箱问题的等价类(英文)

在生产与储运领域,把小长方体货物（盒子）装入大长方体箱子是一项重要的工作.本文涉及的问题是:把相同尺寸（a×b×c）的盒子装到一个箱子X×Y×Z中,使所装入箱子的盒子数量为最大.由于某些条件的限止,有时要求货物只能按一个重力方向进行装箱,从而使装箱问题变为把尺寸相同的2维盒子（a×b）填装到一个2维箱子X×Y中.本文讨论当盒子尺寸（a×b包括 b×a）给定,箱子尺寸充分大时,在本文所给的等价意义下,共有多少种互不等价的箱子X×Y.     

Improved local search algorithms for the rectangle packing problem with general spatial costs

The rectangle packing problem with general spatial costs is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. This problem is very general, and various types of packing problems and scheduling problems can be formulated in this form. For this problem, we have previously presented local search algorithms using a pair of permutations of rectangles to represent a solution. In this paper, we propose speed-up techniques to evaluate solutions in various neighborhoods. Computational results for the rectangle packing problem and a real-world scheduling problem exhibit good prospects of the proposed techniques.     

Two-dimensional cargo overbooking models

This paper introduces two-dimensional (weight and volume) overbooking problems arising mainly in the cargo revenue management, and compares them with one-dimensional problems. It considers capacity spoilage and cargo offloading costs, and minimizes their sum. For one-dimensional problems, it shows that the optimal overbooking limit does not change with the magnitude of the booking requests. In two-dimensional problems, the overbooking limit is replaced by a curve. The curve, along with the volume and weight axes, encircles the acceptance region. The booking requests are accepted if they fall within this region. We present Curve (Cab) and Rectangle (Rab) models. The boundary of the acceptance region in the Cab (resp. Rab) model is a curve (resp. rectangle). The optimal curve for the Cab model is shown to be unique and continuous. Moreover, it can be obtained by solving a series of simple equations. Finding the optimal rectangle for the Rab model is more challenging, so we propose an approximate rectangle. The approximate rectangle is a limiting solution in the sense that it converges to the optimal rectangle as the booking requests increase. The approximate rectangle is numerically shown to yield costs that are very close to the optimal costs.     

Management science applications: Computing and systems analysis: Hamed Kamal ELDIN and Hooshang M. BEHESHTI North-Holland,New York, 1981, xii + 316 pages, $41.50

An acceptance-rejection algorithm for generating random vectors uniformly distributed over (inside or on the surface of) a complex region inserted in a minimal multidimensional rectangle is considered. For regions having simple forms (simplex, hypersphere, hyperellipsoid) several algorithms are presented as well.     

Rectangle exchange transformations

We define rectangle exchange transformations analogously to interval exchange transformations. An interval exchange transformation is a mapping of the unit interval onto itself obtained by cutting the interval up into a finite number of subintervals and rearranging the pieces. A rectangle exchange transformation is a mapping of the unit square onto itself obtained by cutting the square up into a finite number of rectangular pieces and rearranging the pieces. We give a minimality condition for rectangle exchange transformations. We deal with various examples of ergodic rectangle exchange transformations. Related questions are discussed.With 2 Figures     

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.