Advanced methods for the estimation of an unknown projection from a map

This article presents three new methods (M5, M6, M7) for the estimation of an unknown map projection and its parameters. Such an analysis is beneficial and interesting for historic, old, or current maps without information about the map projection; it could improve their georeference. The location similarity approach takes into account the residuals on the corresponding features; the minimum is found using the non-linear least squares. For the shape similarity approach, the minimized objective function ? takes into account the spatial distribution of the features, together with the shapes of the meridians, parallels and other 0D-2D elements. Due to the non-convexity and discontinuity, its global minimum is determined using the global optimization, represented by the differential evolution. The constant values of projection φ _k , λ _k , φ ₁, λ ₀, and map constants R,ΔX,ΔY, α (in relation to which the methods are invariant) are estimated. All methods are compared and the results are presented for the synthetic data as well as for 8 early maps from the Map Collection of the Charles University and the David Rumsay Map Collection. The proposed algorithms have been implemented in the new version of the detectproj software.     

New upper and lower bounds for the eigenvalues of the Sturm-Liouville problem

We derive new inequalities for the eigenvaluesλ _k of the Sturm-Liouville problem?u″+qu=λu, u(0)=u(π)=0 under the usual hypothesis thatq has mean value zero. The estimates give upper and lower bounds of the form |λ _k ?k ²|≤p _1,m k ^?m +P _2,m k ^2m ,k ²≥3‖q‖ _m ,m=1, 2 where ‖q‖ _m is the norm ofq in a Sobolev spaceH ^m (0, π) and theP's are homogeneous polynomials of degree at most 3 in ‖q‖ _m . Such bounds are used in the analysis of the inverse Sturm-Liouville problem.     

Some new sequence spaces derived by the domain of the triple band matrix

Let λ denote any of the classical spaces ?_∞,c,c₀, and ?_p of bounded, convergent, null, and absolutely p-summable sequences, respectively, and let λ(B) also be the domain of the triple band matrix B(r,s,t) in the sequence space λ, where 1<p<∞. The present paper is devoted to studying the sequence space λ(B). Furthermore, the β- and γ-duals of the space λ(B) are determined, the Schauder bases for the spaces c(B), c₀(B), and ?_p(B) are given, and some topological properties of the spaces c₀(B), ?₁(B), and ?_p(B) are examined. Finally, the classes (λ₁(B):λ₂) and (λ₁(B):λ₂(B)) of infinite matrices are characterized, where λ₁∈{?_∞,c,c₀,?_p,?₁} and λ₂∈{?_∞,c,c₀,?₁}.     

Bounds for sums of eigenvalues and applications

Let A be a matrix of order n × n with real spectrum λ₁ ≥ λ₂ ≥ ⋯ ≥ λ_n. Let 1 ≤ k ≤ n − 2. If λ_n or λ₁ is known, then we find an upper bound (respectively, lower bound) for the sum of the k-largest (respectively, k-smallest) remaining eigenvalues of A. Then, we obtain a majorization vector for (λ₁, λ₂,…, λ_n−1) when λ_n is known and a majorization vector for (λ₂, λ₃,…, λ_n) when λ₁ is known. We apply these results to the eigenvalues of the Laplacian matrix of a graph and, in particular, a sufficient condition for a graph to be connected is given. Also, we derive an upper bound for the coefficient of ergodicity of a nonnegative matrix with real spectrum.     

Revisiting the Ziegler–Nichols process dynamics characterization

The Ziegler–Nichols process dynamics characterization is based on the estimation of the ultimate gain k_u and ultimate frequency ω_u. The angle φ of the tangent to the Nyquist curve at the frequency ω_u is introduced, as an additional parameter in the frequency domain. The essential dynamic characteristics of the process can be captured by using the tangent rule, proposed here as an extension of the Ziegler–Nichols approach. The validity of the tangent rule is confirmed by using the PID controller optimization on a test batch consisting of stable, integrating and unstable processes, including dead-time. Parameters k_u, ω_u and φ can be determined from the sustained oscillations, using the phase-locked loop identifier module.     

A simple approach to the problem of 3-D reconstruction

A relatively simple mathematical procedure for the reconstruction of the 3-dimensional (3D) image of the left ventricle (LV) of the heart is presented. The method is based on the assumption that every ray whoch emanates from the midpoint of the long axis of the 3D body crosses the surface boundary of the ventricle at one and only one point. The coordinates r_i, φ_i, θ_i of the data points on, say, the outer boundary, (i.e., the epicardium) are calculated in a spherical coordinate system having its origin in the midpoint of the long axis. The problem of defining the coordinates of a prescribed grid point on the boundary is treated as an interpolation problem for the function r = r(φ, θ), defined in the rectangle 0 ≤ φ ≤ 2π; 0 ≤ θ ≤ π with r_i given in the points (φ_i, θ_i).     

An inexact hybrid projection-proximal point algorithm for solving generalized mixed variational inequalities

In this paper, we investigate an inexact hybrid projection-proximal method for solving a class of generalized mixed variational inequalities in Hilbert spaces. We construct a general inexact hybrid projection-proximal point algorithm, in which an inexact relaxed proximal point step is followed by a suitable orthogonal projection onto a hyperplane. Under some suitable conditions concerned with the pseudomonotone set-valued mapping T, the nonsmooth convex function f and the step size λ_k, we prove the convergence of the inexact hybrid projection-proximal point algorithm for solving generalized mixed variational inequalities in Hilbert spaces.     

A minimum-area circuit forl-selection

We prove tight upper and lower bounds on the area of semelective, when-oblivious VLSI circuits for the problem ofl-selection. The area required to select thelth smallest ofn k-bit integers is found to be heavily dependent on the relative sizes ofl,k, andn. Whenl<2 ^k , the minimal area isA = Θ(minn,l(k-logl)). Whenl≥2 ^k ,A = Θ(2 ^k (logl-k + 1)).     

Constructing vertex-disjoint paths in (n, k)-star graphs

This work describes a novel routing algorithm for constructing a container of width n − 1 between a pair of vertices in an (n, k)-star graph with connectivity n − 1. Since Lin et al. [T.C. Lin, D.R. Duh, H.C. Cheng, Wide diameter of (n, k)-star networks, in: Proceedings of the International Conference on Computing, Communications and Control Technologies, vol. 5, 2004, pp. 160-165] already calculated the wide diameters in (n, n − 1)-star and (n, 1)-star graphs, this study only considers an (n, k)-star with 2 ? k ? n − 2. The length of the longest container among all constructed containers serves as the upper bound of the wide diameter of an (n, k)-star graph. The lower bound of the wide diameter of an (n, k)-star graph with 2 ? k ? ⌊n/2⌋ and the lower bound of the wide diameter of a regular graph with a connectivity of 2 or above are also computed. Measurement results indicate that the wide diameter of an (n, k)-star graph is its diameter plus 2 for 2 ? k ? ⌊n/2⌋, or its diameter plus a value between 1 and 2 for ⌊n/2⌋ + 1 ? k ? n − 2.     

Polynomial time algorithms for computing a representation for minimal unsatisfiable formulas with fixed deficiency

We say a propositional formula F in conjunctive normal form is represented by a formula H and a homomorphism φ, if φ(H)=F. A homomorphism is a mapping consisting of a renaming and an identification of literals. The deficiency of a formula is the difference between the number of clauses and the number of variables. We show that for fixed k?1 and t?1 each minimal unsatisfiable formula with deficiency k can be represented by a formula H with deficiency t and a homomorphism and such a representation can be computed in polynomial time.     

Polynomoperatoren in C k [a,b]

Some estimations for the relative projection constantP(∏ _n+k ^k ,Csik[a,b]) are given. By constructing an associated polynomial operatorL _n :C ⁰[a,b]→∏ _n ⁰ to a given polynomial operatorH _n+k :C ^k [a,b]→∏ _n+k ^k we get a lower bound for the projection constant. An upper bound forP(∏ _n+k ^k ,C ^k [a,b]) is obtained by the determination of the norms of appropriate polynomial operatorsP _n+k :C ^k [a,b]→∏ _n+k ^k . Further we give a convergence property for the sequence (P _n+k ) _n∈?.     

Embedding K-ary Complete Trees into Hypercubes

In this paper, dilated embedding and precise embedding of K-ary complete trees into hypercubes are studied. For dilated embedding, a nearly optimal algorithm is proposed which embeds a K-ary complete tree of height h, T_K(h), into an (h − 1)[log K] + [log (K + 2)]-dimensional hypercube with dilation Max{2, φ(K), φ(K + 2)}. φ(x) = min{λ: Σ^λ_i=0Cⁱ_d ≥ x and d = [log x]}. It is clear that [([log x] + 1)/2] ≤ φ(x) ≤ [log x], for x ≥ 3.) For precise embedding, we show a (K − 1)h + 1-dimensional hypercube is large enough to contain T_K(h) as its subgraph, K ≥ 3.     

Über einen Ordnungsbegriff bei Einbettungsalgorithmen zur Lösung nichtlinearer Gleichungen

For solving the nonlinear systemF(x)=0 by using a continuation method a functionz implicitly defined byH(z, t)=0 has to be determined. In order to obtain approximationsz ^k toz(t _k ) the algorithmz ^k+1:=z ^k ?τ _k p(z ^k ,t _k , τ _k ),t _k+1:=t _k +τ _k , is used. The order of such a functionp is defined in this paper, and for certain classes of algorithms the corresponding orders are determined.     

Characterization of normal forms possessing inverse in the λ-β-η-calculus

The aim of this paper is to generalize a result given by Curry and Feys, who have shown that the only regular combinators possessing inverse in the λ-β-η-calculus are the permutators, whose definition is p=λzλx₁…λx_n(zx_i1…x_in) for n?0 where i₁,…, i_r is a permutation of 1,…, n. Here we extend this characterization to the set of normal forms, showing that the only normal forms possessing inverse in the λ-βη-calculus are the “hereditarily finite permutators” (h.f.p.), whose recursive definition is: if n?0, P_j (1?j?n) are h.f.p. and i₁,…,i_n is a permutation of 1,…, n, then the normal form of P = λzλx₁…λx_n(z(P₁x_i1))… (P_nin) is an h.f.p.     

Simultaneous inner and outer approximation of shapes

For compact Euclidean bodiesP, Q, we define λ(P, Q) to be the smallest ratior/s wherer > 0,s > 0 satisfy \(sQ' \subseteq P \subseteq rQ''\) . HeresQ denotes a scaling ofQ by the factors, andQ′,Q″ are some translates ofQ. This function λ gives us a new distance function between bodies which, unlike previously studied measures, is invariant under affine transformations. If homothetic bodies are identified, the logarithm of this function is a metric. (Two bodies arehomothetic if one can be obtained from the other by scaling and translation.) For integerk ≥ 3, define λ(k) to be the minimum value such that for each convex polygonP there exists a convexk-gonQ with λ(P, Q) ≤ λ(k). Among other results, we prove that 2.118 ... <-λ(3) ≤ 2.25 and λ(k) = 1 + Θ(k ^?2). We give anO(n ² log² n)-time algorithm which, for any input convexn-gonP, finds a triangleT that minimizes λ(T, P) among triangles. However, in linear time we can find a trianglet with λ(t, P)<-2.25. Our study is motivated by the attempt to reduce the complexity of the polygon containment problem, and also the motion-planning problem. In each case we describe algorithms which run faster when certain implicitslackness parameters of the input are bounded away from 1. These algorithms illustrate a new algorithmic paradigm in computational geometry for coping with complexity.     

A note on stutter-invariant PLTL

Peled and Wilke proved that every stutter-invariant propositional linear temporal property is expressible in Propositional Linear Temporal Logic (PLTL) without  ?  (next) operators. To eliminate next operators, a translation τ which converts a stutter-invariant PLTL formula ? to an equivalent formula τ(?) not containing  ?  operators has been given. By τ, for any formula , where φ contains no  ?  operators, a formula with the length of O(n⁴|φ|) is always produced, where n is the number of distinct propositions in ?, and |φ| is the number of symbols appearing in φ. Etessami presented an improved translation τ^′. By τ^′, for , a formula with the length of O(n×n²|φ|) is always produced. We further improve Etessami's result in the worst case to O(n×n²|φ|) by providing a new translation τ^″, and we show that the worst case will never occur.     

Evolution of simple sequence repeats

Simple Sequence Repeats (SSRs) are common and frequently polymorphic in eukaryote DNA. Many are subject to high rates of length mutation in which a gain or loss of one repeat unit is most often observed. Can the observed abundances and their length distributions be explained as the result of an unbiased random walk, starting from some initial repeat length? In order to address this question, we have considered two models for an unbiased random walk on the integers, n (n₀ ⩽ n). The first is a continuous time process (Birth and Death Model or BDM) in which the probability of a transition to n + 1 or n − 1 is λk, with k = n − n₀ + 1 per unit time. The second is a discrete time model (Random Walk Model or RWM), in which a transition is made at each time step, either to n − 1 or to n + 1. In each case the walks start at length n₀, with new walks being generated at a steady rate, S, the source rate, determined by a base substitution rate of mutation from neighboring sequences. Each walk terminates whenever n reaches n₀ − 1 or at some time, T, which reflects the contamination of pure repeat sequences by other mutations that remove them from consideration, either because they fail to satisfy the criteria for repeat selection from some database or because they can no longer undergo efficient length mutations. For infinite T, the results are particularly simple for N(k), the expected number of repeats of length n = k + n₀ − 1, being, for BDM, N(k) = S/kλ, and for RWM, N(k) = 2S. In each case, there is a cut-off value of k for finite T, namely k = Tλ ln2 for BDM and k = 0.57√T for RWM; for larger values of k, N(k) becomes rapidly smaller than the infinite time limit. We argue that these results may be compared with SSR length distributions averaged over many loci, but not for a particular locus, for which founder effects are important. For the data of Beckmann & Weber [(1992), Genomics 12, 627] on GT·AC repeats in the human, each model gives a reasonable fit to the data, with the source at two repeat units (n₀ = 2). Both the absolute number of loci and their length distribution are well represented.     

The Space Complexity of Approximating the Frequency Moments

The frequency moments of a sequence containingm_ielements of typei, 1⩽i⩽n, are the numbersF_k=∑ⁿ_i=1 m^k_i. We consider the space complexity of randomized algorithms that approximate the numbersF_k, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbersF₀,F₁, andF₂can be approximated in logarithmic space, whereas the approximation ofF_kfork⩾6 requiresn^Ω(1)space. Applications to data bases are mentioned as well.     

A parallel routing algorithm on circulant networks employing the Hamiltonian circuit latin square

Double-loop [J. Bermond, F. Comellas, D. Hsu, Distributed Loop Computer Networks: A Survey, J. Parallel and Distributed Computing, Academic Press, 24 (1995) 2-10] and 2-circulant networks (2-CN) [J. Park, Cycle Embedding of Faulty Recursive Circulants, J. of Korea Info. Sci. Soc. 31 (2) (2004) 86-94] are widely used in the design and implementation of local area networks and parallel processing architectures. In this paper, we investigate the routing of a message on circulant networks, that is a key to the performance of this network. We would like to transmit 2k packets from a source node to a destination node simultaneously along paths on G(n; ±s₁, ±s₂, … , ±s_k), where the ith packet traverses along the ith path (1 ? i ? 2k). In order for all packets to arrive at the destination node quickly and securely, the ith path must be node-disjoint from all other paths. For construction of these paths, employing the Hamiltonian circuit latin square (HCLS), a special class of (n × n) matrices, we present O(n²) parallel routing algorithm on circulant networks.