Numerical optimization method for packing regular convex polygons

An algorithm is presented for the approximate solution of the problem of packing regular convex polygons in a given closed bounded domain G so as to maximize the total area of the packed figures. On G a grid is constructed whose nodes generate a finite set W on G, and the centers of the figures to be packed can be placed only at some points of W. The problem of packing these figures with centers in W is reduced to a 0-1 linear programming problem. A two-stage algorithm for solving the resulting problems is proposed. The algorithm finds packings of the indicated figures in an arbitrary closed bounded domain on the plane. Numerical results are presented that demonstrate the effectiveness of the method.     

Numerical optimization methods for packing equal orthogonally oriented ellipses in a rectangular domain

Linear models are constructed for the numerical solution of the problem of packing the maximum possible number of equal ellipses of given size in a rectangular domain R. It is shown that the l _p metric can be used to determine the conditions under which ellipses with mutually orthogonal major axes (orthogonally oriented ellipses) do not intersect. In R a grid is constructed whose nodes generate a finite set T of points. It is assumed that the centers of the ellipses can be placed only at some points of T. The cases are considered when the major axes of all the ellipses are parallel to the x or y axis or the major axes of some of the ellipses are parallel to the x axis and the others, to the y axis. The problems of packing equal ellipses with centers in T are reduced to integer linear programming problems. A heuristic algorithm based on the linear models is proposed for solving the ellipse packing problems. Numerical results are presented that demonstrate the effectiveness of this approach.     

Optimization of multiple covering of a bounded set with circles

Numerical algorithms for the optimization of multiple covering of a bounded set G in the plane P with equal circles are proposed. The variants in which G is a connected bounded set in P or a finite set in P are considered. The circles may be centered at arbitrary points of G or at points belonging to a given set. Minimization of the radius of the given number of circles and minimization of the number of circles of a given radius are considered. Models and solution algorithms are described, and estimates of the solutions provided by most variants are given. Numerical results are presented.     

求解等圆Packing问题的完全拟物算法

沿着拟物的思路进一步研究了具有NP难度的等圆Packing问题.提出了两个拟物策略,第一个是拟物下降算法,第二是让诸圆饼在某种物理定律下做剧烈运动.结合这两个策略,提出了一个统一的拟物算法.当使用N(N=1,2,3,…,100)等圆最紧布局的国际记录对此算法进行检验时,发现对于N=66,67,70,71,77,89这6个算例,本算法找到了比当前国际纪录更优的布局.     

Extending immersions of curves to properly immersed surfaces

Proper generic immersions of compact one-dimensional manifolds in surfaces are studied. Suppose an immersion γ of a collection of circles is given with an even number of double points in a closed surface G. Then γ extends to various proper immersions of surfaces in three-manifolds that are bounded by G. Some of these extensions do not have triple points. The minimum of the genera of the triple point free surfaces is an invariant of the curve. An algorithm to compute this invariant is given.Necessary and suffecient conditions determine if a given collection δ of immersed arcs in a surface F maps to the double points set of a proper immersion. In case the conditions are satisfied, an immersion of F into a three-manifold that depends on δ is constructed explicitly. In the process, the possible triple points of immersed surfaces in three-manifolds are categorized.The techniques are applied to find examples of curves in surfaces that do not bound immersed disks in any three-manifold.     

Apollonian circle packings: number theory

Apollonian circle packings arise by repeatedly filling the interstices between mutually tangent circles with further tangent circles. It is possible for every circle in such a packing to have integer radius of curvature, and we call such a packing an integral Apollonian circle packing. This paper studies number-theoretic properties of the set of integer curvatures appearing in such packings. Each Descartes quadruple of four tangent circles in the packing gives an integer solution to the Descartes equation, which relates the radii of curvature of four mutually tangent circles: . Each integral Apollonian circle packing is classified by a certain root quadruple of integers that satisfies the Descartes equation, and that corresponds to a particular quadruple of circles appearing in the packing. We express the number of root quadruples with fixed minimal element −n as a class number, and give an exact formula for it. We study which integers occur in a given integer packing, and determine congruence restrictions which sometimes apply. We present evidence suggesting that the set of integer radii of curvatures that appear in an integral Apollonian circle packing has positive density, and in fact represents all sufficiently large integers not excluded by congruence conditions. Finally, we discuss asymptotic properties of the set of curvatures obtained as the packing is recursively constructed from a root quadruple.     

Packing Steiner trees: polyhedral investigations

LetG=(V, E) be a graph andT⊆V be a node set. We call an edge setS a Steiner tree forT ifS connects all pairs of nodes inT. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graphG=(V, E) with edge weightsw _e , edge capacitiesc _e ,e∈E, and node setT ₁,…,T _N , find edge setsS ₁,…,S _N such that eachS _k is a Steiner tree forT _k , at mostc _e of these edge sets use edgee for eache∈E, and the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from a routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing problem from a polyhedral point of view and define an associated polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch & cut algorithm. This algorithm is described in our companion paper (in this issue).     

A matching problem with side conditions

Given a graph G, a 2-matching is an assignment of nonnegative integers to the edges of G such that for each node i of G, the sum of the values on the edges incident with i is at most 2. A triangle-free 2-matching is a 2-matching such that no cycle of size 3 in G has the value 1 assigned to all of its edges. In this paper we describe explicity the convex hull of triangle-free 2-matchings by means of its extreme points and of its facets. We give a polynomially bounded algorithm which maximizes a linear function over the set of triangle-free 2-matchings. Finally we discuss some related problems.     

Packing directed cycles efficiently

Let G be a simple digraph. The dicycle packing number of G, denoted ν_c(G), is the maximum size of a set of arc-disjoint directed cycles in G. Let G be a digraph with a nonnegative arc-weight function w. A function ψ from the set C of directed cycles in G to R₊ is a fractional dicycle packing of G if ∑_e∈C∈Cψ(C)?w(e) for each e∈E(G). The fractional dicycle packing number, denoted , is the maximum value of ∑_C∈Cψ(C) taken over all fractional dicycle packings ψ. In case w≡1 we denote the latter parameter by .Our main result is that where n=|V(G)|. Our proof is algorithmic and generates a set of arc-disjoint directed cycles whose size is at least ν_c(G)-o(n²) in randomized polynomial time. Since computing ν_c(G) is an NP-Hard problem, and since almost all digraphs have ν_c(G)=Θ(n²) our result is a FPTAS for computing ν_c(G) for almost all digraphs.The result uses as its main lemma a much more general result. Let F be any fixed family of oriented graphs. For an oriented graph G, let ν_F(G) denote the maximum number of arc-disjoint copies of elements of F that can be found in G, and let denote the fractional relaxation. Then, . This lemma uses the recently discovered directed regularity lemma as its main tool.It is well known that can be computed in polynomial time by considering the dual problem. We present a polynomial algorithm that finds an optimal fractional dicycle packing. Our algorithm consists of a solution to a simple linear program and some minor modifications, and avoids using the ellipsoid method. In fact, the algorithm shows that a maximum fractional dicycle packing with at most O(n²) dicycles receiving nonzero weight can be found in polynomial time.     

An O(n) algorithm for discrete n-point convex approximation with applications to continuous case

Given a bounded real function ? defined on a closed bounded real interval I, the problem is to find a convex function g so as to minimize the supremum of $\text{¦f(t) ? g(t)¦}$ for all t in I, over the class of all convex functions on I. The usual approach is to consider a discrete version of the problem on a grid of (n + 1) points in I, apply a conventional linear program to obtain an optimal solution, and let the grid size go to zero. This paper presents an alternative algorithm of complexity O(n), which is based on the concept of the greatest convex minorant of a function, for computation of a special “maximal” optimal solution to the discrete problem. It establishes the rate of convergence of this optimal solution to a solution of the original problem as the grid size goes to zero. It presents an alternative efficient linear program that generates the maximal optimal solution to the discrete problem. It also gives an O(n) algorithm for the discrete n-point monotone approximation problem.     

On the packing chromatic number of Cartesian products, hexagonal lattice, and trees

The packing chromatic number χ_ρ(G) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into packings with pairwise different widths. Several lower and upper bounds are obtained for the packing chromatic number of Cartesian products of graphs. It is proved that the packing chromatic number of the infinite hexagonal lattice lies between 6 and 8. Optimal lower and upper bounds are proved for subdivision graphs. Trees are also considered and monotone colorings are introduced.     

Quasi-human seniority-order algorithm for unequal circles packing

In the existing methods for solving unequal circles packing problems, the initial configuration is given arbitrarily or randomly, but the impact of different initial configurations for existing packing algorithm to the speed of existing packing algorithm solving unequal circles packing problems is very large. The quasi-human seniority-order algorithm proposed in this paper can generate a better initial configuration for existing packing algorithm to accelerate the speed of existing packing algorithm solving unequal circles packing problems. In experiments, the quasi-human seniority-order algorithm is applied to generate better initial configurations for quasi-physical elasticity methods to solve the unequal circles packing problems, and the experimental results show that the proposed quasi-human seniority-order algorithm can greatly improve the speed of solving the problem.     

Strongly continuous spectral families

Summary We define a strongly continuous family & of bounded projections E(t), t real, on a Banach space X and show that & generates a densely defined closed linear transformation in X given by . T(&) has a real spectrum without eigenvalues and its resolvent operator satisfies a first order growth (G_i). If T₀ is a given closed linear trasformation defined a dense subset of X which has a purely continuous real spectrum and a resolvent operator satisfying the first order growth condition (G_i) then T₀ has a ? resolution of the identity ? &₀ consisting of closed projections E(t) in X. We show that if &₀ is also strongly continuous then T₀=T (&₀). Dedicated to the sixtieth birthday of Professor Edgar. R. Lorch     

A class of uniform functions and its relationship with the class of measurable functions

Borel, Lebesgue, and Hausdorff described all uniformly closed families of real-valued functions on a set T whose algebraic properties are just like those of the set of all continuous functions with respect to some open topology on T. These families turn out to be exactly the families of all functions measurable with respect to some σ-additive and multiplicative ensembles on T. The problem of describing all uniformly closed families of bounded functions whose algebraic properties are just like those of the set of all continuous bounded functions remained unsolved. In the paper, a solution of this problem is given with the help of a new class of functions that are uniform with respect to some multiplicative families of finite coverings on T. It is proved that the class of uniform functions differs from the class of measurable functions.     

Complexity of the packing coloring problem for trees

Packing coloring is a partitioning of the vertex set of a graph with the property that vertices in the i-th class have pairwise distance greater than i. The main result of this paper is a solution of an open problem of Goddard et al. showing that the decision whether a tree allows a packing coloring with at most k classes is NP-complete.We further discuss specific cases when this problem allows an efficient algorithm. Namely, we show that it is decideable in polynomial time for graphs of bounded treewidth and diameter, and fixed parameter tractable for chordal graphs.We accompany these results by several observations on a closely related variant of the packing coloring problem, where the lower bounds on the distances between vertices inside color classes are determined by an infinite nondecreasing sequence of bounded integers.     

A note on Pythagorean hodograph quartic spiral

By using the geometric constraints on the control polygon of a Pythagorean hodograph (PH) quartic curve, we propose a sufficient condition for this curve to have monotone curvature and provide the detailed proof. Based on the results, we discuss the construction of spiral PH quartic curves between two given points and formulate the transition curve of a G² contact between two circles with one circle inside another circle. In particular, we deduce an attainable range of the distance between the centers of the two circles and summarize the algorithm for implementation. Compared with the construction of a PH quintic curve, the complexity of the solution of the equation for obtaining the transition curves is reduced.     

The best generalized inverse of the linear operator in normed linear space

Let X,Y be normed linear spaces, T∈L(X,Y) be a bounded linear operator from X to Y. One wants to solve the linear problem Ax=y for x (given y∈Y), as well as one can. When A is invertible, the unique solution is x=A^-1y. If this is not the case, one seeks an approximate solution of the form x=By, where B is an operator from Y to X. Such B is called a generalised inverse of A. Unfortunately, in general normed linear spaces, such an approximate solution depends nonlinearly on y. We introduce the concept of bounded quasi-linear generalised inverse T^h of T, which contains the single-valued metric generalised inverse T^M and the continuous linear projector generalised inverse T⁺. If X and Y are reflexive, we prove that the set of all bounded quasi-linear generalised inverses of T, denoted by G_H(T), is not empty In the normed linear space of all bounded homogeneous operators, the best bounded quasi-linear generalised inverse T^h of T is just the Moore-Penrose metric generalised inverse T^M. In the case, X and Y are finite dimension spaces Rⁿ and R^m, respectively, the results deduce the main result by G.R. Goldstein and J.A. Goldstein in 2000.     

Fraternal Augmentations of graphs,Coloration and Minors

We introduce classes of graphs with bounded expansion as a generalization of both proper minor closed classes and degree bounded classes. Such classes are based on a new invariant, the greatest reduced average density (grad) of G with rank r, ${\mathrm{\nabla }}_r(G)$. We generalize to these classes some results proved for proper minor closed classes and bounded degree graphs, such as the existence of low tree-width colorings, a linear time algorithm to check subgraph isomorphism for a fixed pattern and homomorphism dualities.     

Bounded sets in topological groups and embeddings

We show that the existence of a non-metrizable compact subspace of a topological group G often implies that G contains an uncountable supersequence (a copy of the one-point compactification of an uncountable discrete space). The existence of uncountable supersequences in a topological group has a strong impact on bounded subsets of the group. For example, if a topological group G contains an uncountable supersequence and K is a closed bounded subset of G which does not contain uncountable supersequences, then any subset A of K is bounded in G?(K?A). We also show that every precompact Abelian topological group H can be embedded as a closed subgroup into a precompact Abelian topological group G such that H is bounded in G and all bounded subsets of the quotient group G/H are finite. This complements Ursul's result on closed embeddings of precompact groups to pseudocompact groups.