Finding the minimum vertex distance between two disjoint convex polygons in linear time

Let V = v₁, v₂, …, v_m and W = w₁, w₂, …, w_n be two linearly separable convex polygons whose vertices are specified by their cartesian coordinates in order. An algorithm with O(m + n) worst-case time complexity is described for finding the minimum euclidean distance between a vertex v₁ in V and a vertex w_j in W. It is also shown that the algorithm is optimal.     

Moments of conjugacy classes of binary words

For each nonempty binary word w=c₁c₂c_q, where c_i{0,1}, the nonnegative integer ∑_i=1^q (q+1−i)c_i is called the moment of w and is denoted by M(w). Let [w] denote the conjugacy class of w. Define M([w])={M(u): u[w]}, N(w)={M(u)−M(w): u[w]} and δ(w)=max{M(u)−M(v): u,v[w]}. Using these objects, we obtain equivalent conditions for a binary word to be an -word (respectively, a power of an -word). For instance, we prove that the following statements are equivalent for any binary word w with |w|2: (a) w is an -word, (b) δ(w)=|w|−1, (c) w is a cyclic balanced primitive word, (d) M([w]) is a set of |w| consecutive positive integers, (e) N(w) is a set of |w| consecutive integers and 0N(w), (f) w is primitive and [w]St.     

Paired-domination in inflated graphs

The inflation G_I of a graph G with n(G) vertices and m(G) edges is obtained from G by replacing every vertex of degree d of G by a clique K_d. A set S of vertices in a graph G is a paired dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired domination number γ_p(G) is the minimum cardinality of a paired dominating set of G. In this paper, we show that if a graph G has a minimum degree δ(G)2, then n(G)γ_p(G_I)4m(G)/[δ(G)+1], and the equality γ_p(G_I) = n(G) holds if and only if G has a perfect matching. In addition, we present a linear time algorithm to compute a minimum paired-dominating set for an inflation tree.     

Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard

Let G=(V,E) be an undirected graph and C a subset of vertices. If the sets B_r(v)∩C, vV (respectively, vVC), are all nonempty and different, where B_r(v) denotes the set of all points within distance r from v, we call C an r-identifying code (respectively, an r-locating-dominating code). We prove that, given a graph G and an integer k, the decision problem of the existence of an r-identifying code, or of an r-locating-dominating code, of size at most k in G, is NP-complete for any r.     

Biinfinite words with maximal recurrent unbordered factors

A finite non-empty word z is said to be a border of a finite non-empty word w if w=uz=zv for some non-empty words u and v. A finite non-empty word is said to be bordered if it admits a border, and it is said to be unbordered otherwise. In this paper, we give two characterizations of the biinfinite words of the form ^ωuvu^ω, where u and v are finite words, in terms of its unbordered factors.

The main result of the paper states that the words of the form ^ωuvu^ω are precisely the biinfinite words w=a₋₂a₋₁a₀a₁a₂ for which there exists a pair (l₀,r₀) of integers with l₀<r₀ such that, for every integers ll₀ and rr₀, the factor a_la_l0a_r0a_r is a bordered word.

The words of the form ^ωuvu^ω are also characterized as being those biinfinite words w that admit a left recurrent unbordered factor (i.e., an unbordered factor of w that has an infinite number of occurrences “to the left” in w) of maximal length that is also a right recurrent unbordered factor of maximal length. This last result is a biinfinite analogue of a result known for infinite words.     

Minimum cost source location problem with vertex-connectivity requirements in digraphs

Given a digraph (or an undirected graph) G=(V,E) with a set V of vertices v with nonnegative real costs w(v), and a set E of edges and a positive integer k, we deal with the problem of finding a minimum cost subset SV such that, for each vertex vV−S, there are k vertex-disjoint paths from S to v. In this paper, we show that the problem can be solved by a greedy algorithm in time in a digraph (or in time in an undirected graph), where n=|V| and m=|E|. Based on this, given a digraph and two integers k and ℓ, we also give a polynomial time algorithm for finding a minimum cost subset SV such that for each vertex vV−S, there are k vertex-disjoint paths from S to v as well as ℓ vertex-disjoint paths from v to S.     

On extended P4-reducible and extended P4-sparse graphs

A graph G was defined in [16] as P₄-reducible, if no vertex in G belongs to more than one chordless path on four vertices or P₄. A graph G is defined in [15] as P₄-sparse if no set of five vertices induces more than one P₄, in G. P₄-sparse graphs generalize both P₄-reducible and the well known class of p₄-free graphs or cographs. In an extended abstract in [11] the first author introduced a method using the modular decomposition tree of a graph as the framework for the resolution of algorithmic problems. This method was applied to the study of P₄-sparse and extended P₄-sparse graphs.

In this paper, we begin by presenting the complete information about the method used in [11]. We propose a unique tree representation of P₄-sparse and a unique tree representation of P₄-reducible graphs leading to a simple linear recognition algorithm for both classes of graphs. In this way we simplify and unify the solutions for these problems, presented in [16–19]. The tree representation of an n-vertex P₄-sparse or a P₄-reducible graph is the key for obtaining O(n) time algorithms for the weighted version of classical optimization problems solved in [20]. These problems are NP-complete on general graphs.

Finally, by relaxing the restriction concerning the exclusion of the C₅ cycles from P₄-sparse and P₄-reducible graphs, we introduce the class of the extended P4-sparse and the class of the extendedP₄-reducible graphs. We then show that a minimal amount of additional work suffices for extending most of our algorithms to these new classes of graphs.     

An element for static, vibration and buckling analysis of thick laminated plates

A conforming finite element formulation of the equations governing composite multilayered plates using Reddy's higher-order theory is presented. The element has eight degrees of freedom, u₀, v₀, w, ∂w/∂x, ∂w/∂y, ∂²w/∂x∂y, γ_x, γ_y, per node. The transverse displacement of the present element is described by a modified bicubic displacement function while the in-plane displacements and shear-rotations are interpolated quadraticly. The element is evaluated for its accuracy in the analysis of static, vibration, and buckling of anisotropic rectangular plates with different lamination schemes and boundary conditions. The conforming finite element described here for the higher-order theory gives fairly accurate results for displacements, stresses, buckling loads, and natural frequencies.     

Efficient enumeration of all minimal separators in a graph

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V, E), Our algorithm requires O(n³R_ab) time, which improves the known result of O(n⁴R_ab) time for solving this problem, where ¦V¦= n and R_ab is the number of minimal a-b separators. The algorithm can be generalized for enumerating all minimal A-B separators that separate non-adjacent vertex sets A, B < V, and it requires O(n²(n − n_A − n_b)R_AB) time in this case, where n_a = ¦A¦, n_B = ¦B¦ and r_AB is the number of all minimal A−B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O(n³R⁺_Σ + n⁴R_Σ), which improves the known result of O(n⁶R_Σ) time, where R_σ is the number of all minimal separators of G and R_ΣR⁺_Σ = ∑_1i, v_j) ER_vivj n − 1)/2 − m)R_Σ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O((n/log n)R_ab) time and the second one runs in time O((n/log n)R⁺_Σ+n log nR_Σ) on a CREW PRAM with O(n³) processors.     

Infinite words and biprefix codes

Let A be an alphabet and ƒ be a right infinite word on A. If ƒ is not ultimately periodic then there exists an infinite set {v_ii0} of (finite) words on A such that ƒ=v₀v₁…v_i…, {v_ii1} is a biprefix code and v_i≠v_j for positive integers i≠j.     

A limit characterization for the number of spanning trees of graphs

In this paper we propose a limit characterization of the behaviour of classes of graphs with respect to their number of spanning trees. Let {G_n} be a sequence of graphs G₀,G₁,G₂,… that belong to a particular class. We consider graphs of the form K_n−G_n that result from the complete graph K_n after removing a set of edges that span G_n. We study the spanning tree behaviour of the sequence {K_n−G_n} when n→∞ and the number of edges of G_n scales according to n. More specifically, we define the spanning tree indicator ({G_n}), a quantity that characterizes the spanning tree behaviour of {K_n−G_n}. We derive closed formulas for the spanning tree indicators for certain well-known classes of graphs. Finally, we demonstrate that the indicator can be used to compare the spanning tree behaviour of different classes of graphs (even when their members never happen to have the same number of edges).     

On canonical number systems

Let be such that d1,p_d=1,p₀2 and . We are proving in this note a new criterion for the pair to be a canonical number system. This enables us to prove that if p₂,…,p_d−1,∑_i=1^dp_i0 and p₀>2∑_i=1^d|p_i|, then is a canonical number system.     

Analytic numerical solution of coupled semi-infinite diffusion problems

In this paper, we consider coupled semi-infinite diffusion problems of the form u_t(x, t)− A² u_xx(x,t) = 0, x> 0, t> 0, subject to u(0,t)=B and u(x,0)=0, where A is a matrix in , and u(x,t), and B are vectors in . Using the Fourier sine transform, an explicit exact solution of the problem is proposed. Given an admissible error and a domain D(x₀,t₀)={(x,t);0≤x≤x₀, t≥t₀ > 0, an analytic approximate solution is constructed so that the error with respect to the exact solution is uniformly upper bounded by in D(x₀, t₀).     

Nonlinear robust stabilization of multi-parameter families of systems

We show that given any family of asymptotically stabilizable LTI systems depending continuously on a parameter that lies in some subset [a₁,b₁]××[a_p,b_p] of , there exists a C⁰ time-varying state feedback law v(t,x) (resp. a C⁰ time-invariant feedback law v(x)) which robustly globally exponentially stabilizes (resp. which robustly stabilizes, not asymptotically) the family. Further, if these systems are obtained by linearizing some nonlinear systems, then v(t,x) locally exponentially stabilizes these nonlinear systems. Finally, v(t,x) globally exponentially stabilizes any time-varying system which switches “slowly enough” between the given LTI systems.     

On the sensitivity of camera calibration

The orientation position errors of an object's coordinate frame are determined when the offset of image centre and lens distortion are not included in the calibration process. The orientation and position errors are [(u₀)² + (v₀)²]^0.5/f and [(u²₀+v²₀)T²_z + (u²₀T²_z + v²₀T_y²)]^0.5/f, respectively, where f is the focal length, (u₀, v₀) is the offset of image centre and (T_x T_y T_z) is the position of an object. We also obtain the following conclusions: (a) The offset of image centre has little effect on the determinations of the position and orientation of a coordinate frame; (b) the lens distortion will not dramatically change the position and orientation of a coordinate frame; (c) the scale factor has a great effect on the position of a coordinate frame, and on the accuracy of measurement; (d) the offset of image centre is more sensitive than the lens distortion on the determinations of the position and orientation of a coordinate frame. Finally, some experimental results are given to demonstrate the theoretical analysis given in this paper.     

A multi-tree routing scheme using acyclic orientations

We propose a mathematical model for fault-tolerant routing based on acyclic orientations, or acorns, of the underlying network G=(V,E). The acorn routing model applies routing tables that store the set of parent pointers associated with each out-neighborhood defined by the acorn. Unlike the standard single-parent sink-tree model, which is vulnerable to faults, the acorn model affords a full representation of the entire network and is able to dynamically route around faults. This fault tolerance is achieved when using the acorn model as a multi-tree generator for gathering data at a destination node, as well as an independent tree generator for global point-to-point communication. A fundamental fault-tolerant measure of the model is the capacity of an acorn, i.e., the largest integer k such that each vertex outside the neighborhood N(v) of the destination v has at least k parent pointers. A capacity-k acorn A to destination v is k-vertex fault-tolerant to v. More strongly, we show A supports a k independent sink-tree generator, i.e., the parent pointers of each vertex w V−N(v) can be partitioned into k nonempty classes labeled 1,2,…,k such that any set of sink trees T₁,T₂,…,T_k are pairwise independent, where tree T_i is a sink tree generated by parent pointers labeled i together with the parent pointers into v. We present an linear time optimization algorithm for finding an acorn A of maximum capacity in graphs, based upon a minimax theorem. We also present efficient algorithms that label the parent pointers of capacity-k acorn A, yielding a k-independent sink tree generating scheme.     

Nonexistence of finite-dimensional filters for conditional statistics of the cubic sensor problem

Consider the cubic sensor dx = dw, dy = x³dt + dv where w, v are two independent Brownian motions. Given a function φ(x) of the state x let φ_t(x) denote the conditional expectation given the observations y_s, 0 s t. This paper consists of a rather detailed discussion and outline of proof of the theorem that for nonconstant φ there cannot exist a recursive finite-dimensional filter for φ driven by the observations.     

Blossoms are polar forms

Consider the functions H(t):=t² and h(u,v):=uv. The identity H(t)=h(t,t) shows that h is the restriction of h to the diagonal u=v in the uv-plane. Yet, in many ways, a bilinear function like h is simpler than a homogeneous quadratic function like H. More generally, if F(t) is some n-ic polynomial function, it is often helpful to study the polar form of F, which is the unique symmetric, multiaffine function ƒ(u_1,…u_n) satisfying the identity F(t)=f(t,…,t). The mathematical theory underlying splines is one area where polar forms can be particularly helpful, because two pieces F and G of an n-ic spline meet at a point r with C^k parametric continuity if and only if their polar forms ƒ and g agree on all sequences of n arguments that contain at least n-k copies of r.

The polar approach to the theory of splines emerged in rather different guises in three independent research efforts: Paul de Faget Casteljau called it ‘shapes through poles’; Carl de Boor called it ‘B-splines without divided differences’; and Lyle Ramshaw called it ‘blossoming’. This paper reviews the work of de Casteljau, de Boor, and Ramshaw in an attempt to clarify the basic principles that underly the polar approach. It also proposes a consistent system of nomenclature as a possible standard.     

On the error in Padé approximations for functions defined by Stieltjes integrals

Consdier I(z) = ∫^b_a w(t)f(t, z) dt, f(t, z) = (1 + t/z)⁻¹. It is known that generalized Gaussian quadrature of I(z) leads to approximations which occupy the (n, n + r − 1) positions of the Padé matrix table for I(z). Here r is a positive integer or zero. In a previous paper the author developed a series representation for the error in Gaussian quadrature. This approach is now used to study the error in the Padé approximations noted. Three important examples are treated. Two of the examples are generalized to the case where f(t, z) = (1 + t/z)^−v.     

Analytic-numerical solutions with a priori error bounds for time-dependent mixed partial differential problems

The aim of this paper is double. First, we point out that the hypothesis D(t₁)D(t₂) = D(t₂)D(t₁) imposed in [1] can be removed. Second, a constructive method for obtaining analytic-numerical solutions with a prefixed accuracy in a bounded domain Ω(t₀,t₁) = [0,p] × [t₀,t₁], for mixed problems of the type u_t(x,t) − D(t)u_xx(x,t) = 0, 0 < x < p, t> 0, subject to u(0,t) = u(p,t) = 0 and u(x,0) = F(x) is proposed. Here, u(x,t) and F(x) are r-component vectors, D(t) is a C^{r × r} valued analytic function and there exists a positive number δ such that every eigenvalue z of (1/2) (D(t) + D(t)^H) is bigger than δ. An illustrative example is included.