A simulated annealing approach to the nesting problem in the textile manufacturing industry

The nesting problem in the textile industry is the problem of placing a set of irregularly shaped pieces (calledstencils) on a rectangularsurface, such that no stencils overlap and that thetrim loss produced when cutting out the stencils is minimized. Certain constraints may put restrictions on the positions and orientation of some stencils in the layout but, in general, the problem is unconstrained. In this paper, an algorithmic approach using simulated annealing is presented covering a wide variety of constraints which may occur in the industrial manufacturing process. The algorithm has high performance, is quite simple to use, is extensible with respect to the set of constraints to be met, and is easy to implement.The work of this author was supported in part by grant Le 491/3-1 from the German Research Association (DFG).     

On the equipartition of plane convex bodies and convex polygons

In this paper we consider the problem of partitioning a plane compact convex body into equal-area parts, i.e., an equipartition, by means of chords. We prove two basic results that hold with some specific exceptions: (a) When chords are pairwise non-crossing, the dual tree of the partition has to be a path, (b) A convex n-gon admits no equipartition produced by more than n chords having a common interior point.     

Matching planar maps

The subject of this paper are algorithms for measuring the similarity of patterns of line segments in the plane, a standard problem in, e.g., computer vision, geographic information systems, etc. More precisely, we define feasible distance measures that reflect how close a given pattern H is to some part of a larger pattern G. These distance measures are generalizations of the well-known Fréchet distance for curves. We first give an efficient algorithm for the case that H is a polygonal curve and G is a geometric graph. Then, slightly relaxing the definition of distance measure, we give an algorithm for the general case where both, H and G, are geometric graphs.     

Diffusion-controlled smoulder propagation in a semi-infinite solid: A numerical solution

The propagation of a thin two-dimensional smouldering reactionfront (SRF) parallel to a plane surface in a semi-infinite solidfuel is considered. Combustion is controlled by oxidizer diffusionthrough the porous burnt material behind the SRF. The modelgives rise to a free boundary problem as the position of theSRF is to be determined as part of the solution. The Burke-Schumanncondition of the oxidizer concentration vanishing on the SRFis adopted. Different forms of the plane surface boundary conditionare considered. The governing linear p.d.e., which holds inan unknown domain, is converted into a nonlinear p.d.e. overa fixed domain by Alt's method, in which the free boundary conditionsare satisfied by a jump condition. The position of the SRF andthe oxidizer concentration distribution behind it are determined.It is shown that the shape of the SRF is asymptotically parabolic,consistent with analytic and experimental results. Contoursof equal oxygen concentration are presented.     

The method of integral equation for scattering problem with a mixed crack

We consider the scattering of an electromagnetic time‐harmonic plane wave by an infinite cylinder having a mixed open crack (or arc) in R² as the cross section. The crack is made up of two parts, and one of the two parts is (possibly) coated by a material with surface impedance λ. We transform the scattering problem into a system of boundary integral equations by adopting a potential approach, and establish the existence and uniqueness of a weak solution to the system by the Fredholm theory. Copyright © 2011 John Wiley & Sons, Ltd.     

Edge Green’s functions on a branched surface. Asymptotics of solutions of coordinate and spectral equations

The problems of diffraction by a slit or a strip having ideal boundary conditions, and some other problems, can be reduced to the problem of wave propagation on a multisheet surface by applying the method of reflections. Further simplifications of the problem can be achieved by applying an embedding formula. As a result, the solution of the problem with a plane wave incidence becomes expressed in terms of the edge Green’s functions, i.e., in terms of the fields generated by dipole sources localized at branchpoints of the surface. The present paper is devoted to finding the edge Green’s functions. For this problem, two sets of differential equations, namely, the coordinate and spectral equations, are used. The properties of solutions of these equations are studied. Bibliography: 9 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 342, 2007, pp. 233–256.     

Shape design sensitivity analysis of plates and plane elastic solids under unilateral constraints

The local dependence of static response and eigenvalues on the shape of plates and plane elastic solids is characterized. The so-called material derivative method is used. The shape sensitivity analysis includes, besides linear problems, nonlinear problems with unilateral conditions, e.g., the frictionless contact problem for an elastic body on a rigid foundation. The results on shape sensitivity analysis can be used to obtain expressions for variations of integral functionals that arise in structural optimization problems.The authors are indebted to Professor N. Olhoff and Dr. M. P. Bendsøe for stimulating discussions and valuable comments on design sensitivity analysis.     

Least-squares fitting of circles and ellipses

Fitting circles and ellipses to given points in the plane is a problem that arises in many application areas, e.g., computer graphics, coordinate meteorology, petroleum engineering, statistics. In the past, algorithms have been given which fit circles and ellipses insome least-squares sense without minimizing the geometric distance to the given points.In this paper we present several algorithms which compute the ellipse for which thesum of the squares of the distances to the given points is minimal. These algorithms are compared with classical simple and iterative methods.Circles and ellipses may be represented algebraically, i.e., by an equation of the formF(x)=0. If a point is on the curve, then its coordinates x are a zero of the functionF. Alternatively, curves may be represented in parametric form, which is well suited for minimizing the sum of the squares of the distances.Dedicated to Åke Björck on the occasion of his 60th birthday     

Fuzzy part coding for group technology

Contemporary Group Technology (GT) methods apply coding schemes as a popular method for capturing the design and manufacturing information pertinent to the parts to be grouped. Coding schemes are very popular and many different coding systems are commercially available. The main disadvantage of current coding systems, however, is their generality and lack of informative representation of the parts.This paper presents a new methodology for coding parts using fuzzy codes. The methodology is general and applies to attributes that have a crisp value (e.g., “length”, “ratio of length to diameter”), an interval value (e.g., “tolerance”, “surface roughness”) or a fuzzy value (e.g., “primary shape”). The methodology considers the range of attributes' values relevant for the grouping, and therefore, is tuned and adjusted to the specific collection of parts of interest. This method creates a more informative coding scheme which leads to improved variant process planning methods, scheduling and inventory control as well as other manufacturing functions that utilize GT.     

A PTAS for minimum <Emphasis Type="Italic">d</Emphasis>-hop connected dominating set in growth-bounded graphs

In this paper, we design the first polynomial time approximation scheme for d-hop connected dominating set (d-CDS) problem in growth-bounded graphs, which is a general type of graphs including unit disk graph, unit ball graph, etc. Such graphs can represent majority types of existing wireless networks. Our algorithm does not need geometric representation (e.g., specifying the positions of each node in the plane) beforehand. The main strategy is clustering partition. We select the d-CDS for each subset separately, union them together, and then connect the induced graph of this set. We also provide detailed performance and complexity analysis.     

Projectively flat Finsler 2-spheres of constant curvature

After recalling the structure equations of Finsler structures on surfaces, I define a notion of "generalized Finsler structure" as a way of microlocalizing the problem of describing Finsler structures subject to curvature conditions. I then recall the basic notions of path geometry on a surface and define a notion of "generalized path geometry" analogous to that of "generalized Finsler structure". I use these ideas to study the geometry of Finsler structures on the 2-sphere that have constant Finsler-Gauss curvature K and whose geodesic path geometry is projectively flat, i.e., locally equivalent to that of straight lines in the plane. I show that, modulo diffeomorphism, there is a 2-parameter family of projectively flat Finsler structures on the sphere whose Finsler-Gauss curvature K is identically 1.     

A planar minimax alogrithm for analysis of coordinate measurements

We characterize the solution of the following problem and describe an algorithm for numerically solving it. Two sets ofN points in the plane, labeled 1,...,N, are given: a fixed set of nominal points and a set of measured points. We wish to transform the messured points as a whole, by translation and rotation, so that the maximal distance between corresponding points in the two sets is minimized. This algorthm provides an accept-reject criterion that may be used together with a coordinate measuring machine to determine if two mating parts will fit, or if a part is sufficiently close to its ideal measurements. A weighted version, suitable for point-dependent tolerances, is also discussed, as is optimal joint scalling of the data.     

On the solution of Maxwell's equations in polygonal domains

This paper is concerned with the structure of the singular and regular parts of the solution of time‐harmonic Maxwell's equations in polygonal plane domains and their effective numerical treatment. The asymptotic behaviour of the solution near corner points of the domain is studied by means of discrete Fourier transformation and it is proved that the solution of the boundary value problem does not belong locally to H² when the boundary of the domain has non‐acute angles. A splitting of the solution into a regular part belonging to the space H², and an explicitly described singular part is presented. For the numerical treatment of the boundary value problem, we propose a finite element discretization which combines local mesh grading and the singular field methods and derive a priori error estimates that show optimal convergence as known for the classical finite element method for problems with regular solutions. Copyright © 2006 John Wiley & Sons, Ltd.     

Curvature and uniformization

We approach the problem of uniformization of general Riemann surfaces through consideration of the curvature equation, and in particular the problem of constructing Poincaré metrics (i.e., complete metrics of constant negative curvature) by solving the equation Δu-e ^2u=K_o(z) on general open surfaces. A few other topics are discussed, including boundary behavior of the conformal factore ^2u giving the Poincaré metric when the Riemann surface has smoothly bounded compact closure, and also a curvature equation proof of Koebe's disk theorem. Research supported in part by NSF Grant DMS-9971975 and also at MSRI by NSF grant DMS-9701755. Research supported in part by NSF Grant DMS-9877077     

IDENTIFICATION OF EXTRAPOLATION SPACES FOR UNBOUNDED OPERATORS

Abstract

Abstract extrapolation spaces for strongly continuous semigroups of linear operators on Banach spaces have been constructed by various methods (see, e.g., [Am (1988)], [DaP-Gr (1984)], [Na (1983)], [Ne (1992)], [Wa (1986)]). Usually they appear as “artefacts” used in some intermediate step in order to solve the Cauchy problem on the original space. Only in a few cases (see the papers by the Dutch school on X ^⊙*, e.g., [Ne (1992)]), and in sharp contrast to the situation for interpolation spaces (see, e.g., [Gr (1969)], [DiB (1991)], [Lu (1985)], [Ac-Te (1987)]), the extrapolation spaces have been identified in a concrete way. It is our intention to fill this gap and subsequently to give an application of the extrapolation method to a perturbation problem.     

A game-theoretic approach for downgrading the?1-median in the?plane with Manhattan metric

This paper deals with downgrading the 1-median, i.e., changing values of parameters within certain bounds such that the optimal objective value of the location problem with respect to the new values is maximized. We suggest a game-theoretic view at this problem which leads to a characterization of an optimal solution. This approach is demonstrated by means of the Downgrading 1-median problem in the plane with Manhattan metric and implies an O(nlog²n)\mathcal {O}(n\log^{2}n) time algorithm for this problem.     

Strategies for polyhedral surface decomposition: An experimental study

This paper addresses the problem of decomposing a complex polyhedral surface into a small number of “convex” patches (i.e., boundary parts of convex polyhedra). The corresponding optimization problem is shown to be NP-complete and an experimental search for good heuristics is undertaken.     

Continuum percolation with steps in the square or the disc

In 1961 Gilbert defined a model of continuum percolation in which points are placed in the plane according to a Poisson process of density 1, and two are joined if one lies within a disc of area A about the other. We prove some good bounds on the critical area A_c for percolation in this model. The proof is in two parts: First we give a rigorous reduction of the problem to a finite problem, and then we solve this problem using Monte‐Carlo methods. We prove that, with 99.99% confidence, the critical area lies between 4.508 and 4.515. For the corresponding problem with the disc replaced by the square we prove, again with 99.99% confidence, that the critical area lies between 4.392 and 4.398. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

A study of the perturbed stress state of a closed cylindrical shell with a system of part-through transverse cracks

We study the elastic equilibrium of a closed infinite circular cylindrical shell with a system of surface cracks of identical length and depth. We use the method of singular integral equations together with the modeling of solid matter in the plane of a part-through crack by irregularly distributed “line springs”. We conduct a numerical analysis of the variation of the relative stress intensity factor at the center of a crack as a function of the parameters of a crack and the number of cracks. We study cracks located on both the interior and exterior surface of the shell. Translated fromMatematicheskie Metody i Fiziko-Mekhanicheskie Polya, No. 37, 1994, pp. 63–65.