基于自适应遗传模拟退火算法的矩形件排样

研究一种自适应遗传模拟退火算法,应用于矩形件优化排样问题。以整数编码矩形件的排样序列,采用经验选择与随机生成相结合的策略构造初始种群。运用自适应交叉和变异概率动态地控制遗传算法的收敛速度,通过模拟退火算法引导全局最优搜索,采用启发式最低水平线择优算法对排样序列进行解码,形成排样方式。多组对比实验结果表明,自适应遗传模拟退火算法求解速度较快,可以有效提高板材的利用率。     

基于遗传模拟退火算法的矩形件优化排样

为了探索更高效的矩形件优化排样方法,提出了一种改进的自适应遗传模拟退火算法。设计了基于矩形件的排样次序及旋转变量的两层染色体编码方法,并采用基于临界多边形的BL定位策略实现矩形件的布局;通过构造启发式算法生成排样初始种群,然后各个种群之间通过相互竞争实现优秀个体的迁移与共享,最终搜索到最优解。标准测试问题的实验结果验证了所提算法的可行性与有效性。     

Covering a set of points in a plane using two parallel rectangles

In this paper we consider the problem of finding two parallel rectangles in arbitrary orientation for covering a given set of n points in a plane, such that the area of the larger rectangle is minimized. We propose an algorithm that solves the problem in O(n³) time using O(n²) space. Without altering the complexity, our approach can be used to solve another optimization problem namely, minimize the sum of the areas of two arbitrarily oriented parallel rectangles covering a given set of points in a plane.     

Parallel computational geometry of rectangles

Rectangles in a plane provide a very useful abstraction for a number of problems in diverse fields. In this paper we consider the problem of computing geometric properties of a set of rectangles in the plane. We give parallel algorithms for a number of problems usingn processors wheren is the number of upright rectangles. Specifically, we present algorithms for computing the area, perimeter, eccentricity, and moment of inertia of the region covered by the rectangles inO(logn) time. We also present algorithms for computing the maximum clique and connected components of the rectangles inO(logn) time. Finally, we give algorithms for finding the entire contour of the rectangles and the medial axis representation of a givenn × n binary image inO(n) time. Our results are faster than previous results and optimal (to within a constant factor).The work of Sung Kwan Kim was supported by NSF Grant CCR-87-03196 and the work of D. M. Mount was partially supported by National Science Foundation Grant CCR-89-08901.     

Interpolation in a derivative strip

This paper is concerned with data interpolation subject to a strip condition on the first order derivative. Using spline functions on refined grids we can offer computational methods which are always successful in constructing interpolants of the desired type. Especially, the placement of the additional knots in refining the grids is of importance.     

Labeling points with given rectangles

In this paper, we consider the following problem: Given n pairs of a point and an axis-parallel rectangle in the plane, place each rectangle at each point in order that the point lies on the corner of the rectangle and the rectangles do not intersect. If the size of the rectangles may be enlarged or reduced at the same factor, maximize the factor. This paper generalizes the results of Formann and Wagner [Proc. 7th Annual ACM Symp. on Comput. Geometry (SoCG'91), 1991, pp. 281-288]. They considered the uniform squares case and showed that there is no polynomial time algorithm less than 2-approximation. We present a 2-approximation algorithm of the non-uniform rectangle case which runs in O(n²logn) time and takes O(n²) space. We also show that the decision problem can be solved in O(nlogn) time and space in the RAM model by transforming the problem to a simpler geometric problem.     

Parallel computational geometry of rectangles

Rectangles in a plane provide a very useful abstraction for a number of problems in diverse fields. In this paper we consider the problem of computing geometric properties of a set of rectangles in the plane. We give parallel algorithms for a number of problems usingn processors wheren is the number of upright rectangles. Specifically, we present algorithms for computing the area, perimeter, eccentricity, and moment of inertia of the region covered by the rectangles inO(logn) time. We also present algorithms for computing the maximum clique and connected components of the rectangles inO(logn) time. Finally, we give algorithms for finding the entire contour of the rectangles and the medial axis representation of a givenn × n binary image inO(n) time. Our results are faster than previous results and optimal (to within a constant factor).     

Time- and space-optimal contour computation for a set of rectangles

We present the first time- and space-optimal algorithm for the problem of computing the contours of the disjoint polygons defined by the union of n rectangles in the plane. It requires O(n log n+e) time and O(n) space, where e is the total number of edges in the contour cycles. The space optimality of the solution is demonstrated by way of a combinatorial argument.     

Optimal placement of rectangles on a plane with fixed objects

Consider a region on a plane with a set of points with positive weights and rectangles that have to be place in that region without intersections. Either the maximal sum of weights of the points in rectangles or the total sum must be minimal. We consider the case of two rectangles. The original continuous problem is reduced to a discrete one by introducing equivalence classes. We propose polynomial combinatorial algorithms for solving the problem. We conduct a computational experiment to compare the efficiency of developed algorithms with the IBM ILOG CPLEX suite with an integer programming model.     

Algorithms for covering polygons by rectangles

The polygons on the pattern generator used to produce masks for integrated circuits must be covered by the smallest possible number of rectangles. Two algorithms were elaborated to enable this task to be computerized. One of these algorithms is for general polygons, the other for orthogonal ones - the latter is quicker and more effective. Examples are given to demonstrate the effectiveness and the processing time of the program, which is part of the designer system for microelectronics (MICAD) elaborated at the Central Research Institute for Physics of the Hungarian Academy of Sciences.     

A parallel algorithm to construct a dominance graph on nonoverlapping rectangles

A parallel algorithm to generate the dominance graph on a collection of nonoverlapping iso-oriented rectangles is presented. This graph arises from the constraint graph commonly used in compaction algorithms for VLSI circuits. The dominance graph expresses the notion of aboveness on a collection of nonoverlapping rectangles: it is the directed graph which contains an edge from a rectangleb to rectanglec iffc is immediately aboveb. The algorithm is based on the divide and conquer paradigm; in the EREW PRAM model, it has time complexityO(log² n), usingn/logn processors. Its processor-time product isO(nlogn), which is optimal.     

An optimal algorithm for reporting visible rectangles

We consider the following problem as defined by Grove et al. [Internat. J. Comput. Geom. Appl. 9 (1999) 207-217]: Given a set of n isothetic rectangles in 3D space determine the subset of rectangles, that are not completely hidden. We present an optimal algorithm for this problem that runs in O(nlogn) time and O(n) space. Our result is an improvement over the one of Grove et al. by a logarithmic factor in storage and is achieved by using a different approach. An analogous approach gives non-trivial solutions for other kinds of objects too.     

Stars,maximal rectangles,lattices: a new perspective on Q-analysis

A new star-hub structure of binary relations is discussed in the context of the methodology of Q-analysis, and parallels are drawn with maximal rectangles and Galois lattice structures. Although these structures generalize those of Q-analysis, there remain problems due to the very large number of star-hub pairs generated by fairly modest data sets. It is argued that more theory is necessary, and some possibilities are discussed. It is suggested that the criteria for defining new structures will come most fruitfully from the study of the relationship between backcloth and the ways it constrains traffic. Finally, it is argued that these combinatorial structures are still not sufficient to fully describe complex systems and that for this one needs to consider polyhedra in the context of N-ary relations.     

Optimal VLSI graph embeddings in variable aspect ratio rectangles

We generalize earlier results in VLSI layout theory by considering variable aspect ratio embeddings for VLSI graphs. By aspect ratio we mean the ratio of the length of the longer side to the length of the shorter side of the bounding rectangle of the embedding. Our results are based on separators and bifurcators. We obtain embeddings with existentially optimal area and any desired aspect ratio. Additionally, we can obtain either bounded capacitive delay or existentially optimal minimax edge length in the embeddings; both of these features reduce delays in the circuit. A special feature of our results on minimax edge length is that they unify earlier separator- and bifurcator-based results for square embeddings, and also provide a simplified lower bound proof.     

Digital parallelism, perpendicularity, and rectangles

The slope of digital line segments is defined and an algorithm to evaluate it is presented. Parallelism and perpendicularity of two digital line segments are also defined. Finally, rectangular digital regions are defined and characterized, and an algorithm that determines whether or not a given digital region is a digital rectangle is presented.     

绿色包装结构设计在绿色包装设计中的作用

文章从绿色包装结构设计谈起,通过包装结构在包装设计中的重要性来体现绿色包装结构设计在绿色包装设计的重要性,并详细阐述了如何从包装结构设计入手进行绿色环保结构设计,提出了从根本上解决绿色包装设计问题的设计思路和设计方法。     

Optimal VLSI graph embeddings in variable aspect ratio rectangles

We generalize earlier results in VLSI layout theory by considering variable aspect ratio embeddings for VLSI graphs. By aspect ratio we mean the ratio of the length of the longer side to the length of the shorter side of the bounding rectangle of the embedding. Our results are based on separators and bifurcators. We obtain embeddings with existentially optimal area and any desired aspect ratio. Additionally, we can obtain either bounded capacitive delay or existentially optimal minimax edge length in the embeddings; both of these features reduce delays in the circuit.A special feature of our results on minimax edge length is that they unify earlier separator- and bifurcator-based results for square embeddings, and also provide a simplified lower bound proof.This research was supported in part by the Semiconductor Research Corporation under contract SRC RSCH 84-06-049 and by an IBM Faculty Development Award to Vijaya Ramachandran. Preliminary versions of portions of this work were presented at the Sixteenth Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, February 1985, and at the 1985 Conference on Information Sciences and Systems, Baltimore, MD, March 1985.     

Packing items from a triangular distribution

We consider the problem of packing n items, which are drawn according to a probability distribution whose density function is triangular in shape, into bins of unit capacity. For triangles which represent density functions whose expectation is 1/p for p = 3, 4, 5,…, we give a packing strategy for which the ratio of the number of bins used in the packing to the expected total size of the items asymptotically approaches 1.     

Packing identical spheres into a cylinder

The paper deals with the optimization problem of packing identical spheres into a cylinder of minimal height. A mathematical model of the problem is constructed and its characteristics are considered. On the ground of characteristics, a strategy of searching for an approximation to a global minimum is offered. The strategy includes a special search tree construction, a modification of the Zoutendijk method of feasible directions to calculate local minima, and a modification of the decremental neighborhood method to search for an approximation to a global minimum. Numerical examples and performance analysis of solutions are given. On the basis of the mathematical model and numerical experiment, a number of conclusions are drawn.