Circle approximation using LN Bézier curves of even degree and its application

We present an approximation method of circular arcs using linear-normal (LN) Bézier curves of even degree, four and higher. Our method achieves G^m$G^m$ continuity for endpoint interpolation of a circular arc by a LN Bézier curve of degree 2m  , for m=2,3$m=2,3$. We also present the exact Hausdorff distance between the circular arc and the approximating LN Bézier curve. We show that the LN curve has an approximation order of 2m+2$2m+2$, for m=2,3$m=2,3$. Our approximation method can be applied to offset approximation, so obtaining a rational Bézier curve as an offset approximant. We derive an algorithm for offset approximation based on the LN circle approximation and illustrate our method with some numerical examples.     

Every point is critical

We show that, for any compact Alexandrov surface S$S$ (without boundary) and any point y$y$ in S$S$, there exists a point x$x$ in S$S$ for which y$y$ is a critical point. Moreover, we prove that uniqueness characterizes the surfaces homeomorphic to the sphere among smooth orientable surfaces.     

Necessary and sufficient conditions for rational quartic representation of conic sections

Conic section is one of the geometric elements most commonly used for shape expression and mechanical accessory cartography. A rational quadratic Bézier curve is just a conic section. It cannot represent an elliptic segment whose center angle is not less than π$\pi$. However, conics represented in rational quartic format when compared to rational quadratic format, enjoy better properties such as being able to represent conics up to 2π$2\pi$ (but not including 2π$2\pi$) without resorting to negative weights and possessing better parameterization. Therefore, it is actually worth studying the necessary and sufficient conditions for the rational quartic Bézier representation of conics. This paper attributes the rational quartic conic sections to two special kinds, that is, degree-reducible and improperly parameterized; on this basis, the necessary and sufficient conditions for the rational quartic Bézier representation of conics are derived. They are divided into two parts: Bézier control points and weights. These conditions can be used to judge whether a rational quartic Bézier curve is a conic section; or for a given conic section, present positions of the control points and values of the weights of the conic section in form of a rational quartic Bézier curve. Many examples are given to show the use of our results.     

Equivariant Willmore surfaces in conformal homogeneous three spaces

The complete classification of homogeneous three spaces is well known for some time. Of special interest are those with rigidity four which appear as Riemannian submersions with geodesic fibres over surfaces with constant curvature. Consequently their geometries are completely encoded in two values, the constant curvature, c$c$, of the base space and the so called bundle curvature, r$r$. In this paper, we obtain the complete classification of equivariant Willmore surfaces in homogeneous three spaces with rigidity four. All these surfaces appear by lifting elastic curves of the base space. Once more, the qualitative behaviour of these surfaces is encoded in the above mentioned parameters (c,r)$(c,r)$. The case where the fibres are compact is obtained as a special case of a more general result that works, via the principle of symmetric criticality, for bundle-like conformal structures in circle bundles. However, if the fibres are not compact, a different approach is necessary. We compute the differential equation satisfied by the equivariant Willmore surfaces in conformal homogeneous spaces with rigidity of order four and then we reduce directly the symmetry to obtain the Euler Lagrange equation of 4r²$4r^2$-elasticae in surfaces with constant curvature, c$c$. We also work out the solving natural equations and the closed curve problem for elasticae in surfaces with constant curvature. It allows us to give explicit parametrizations of Willmore surfaces and Willmore tori in those conformal homogeneous 3-spaces.     

Tournaments associated with multigraphs and a theorem of Hakimi

A tournament of order n$n$ is usually considered as an orientation of the complete graph _Kn$K_n$. In this note, we consider a more general definition of a tournament that we call aC$C$-tournament, where C$C$ is the adjacency matrix of a multigraph G$G$, and a C$C$-tournament is an orientation of G$G$. The score vector of a C$C$-tournament is the vector of outdegrees of its vertices. In 1965 Hakimi obtained necessary and sufficient conditions for the existence of a C$C$-tournament with a prescribed score vector R$R$ and gave an algorithm to construct such a C$C$-tournament which required, however, some backtracking. We give a simpler and more transparent proof of Hakimi’s theorem, and then provide a direct construction of such a C$C$-tournament which works even for weighted graphs.     

Weak convergence of censored and reflected stable processes

It is shown that if a sequence of open n$n$-sets _Dk$D_k$ increases to an open n$n$-set D$D$ then reflected stable processes in _Dk$D_k$ converge weakly to the reflected stable process in D$D$ for every starting point x$x$ in D$D$. The same result holds for censored α$\alpha$-stable processes for every x$x$ in D$D$ if D$D$ and _Dk$D_k$ satisfy the uniform Hardy inequality. Using the method in the proof of the above results, we also prove the weak convergence of reflected Brownian motions in unbounded domains.     

The Quicksort process

Quicksort on the fly returns the input of n$n$ reals in increasing natural order during the sorting process. Correctly normalized the running time up to returning the l$l$-th smallest out of n$n$ seen as a process in l$l$ converges weakly to a limiting process with path in the space of cadlag functions.     

On testing Hamiltonicity of graphs

Let us fix a function f(n)=o(nlnn)$f\left(n\right)=o(nlnn)$ and real numbers 0≤α<β≤1$0\le \alpha <\beta \le 1$. We present a polynomial time algorithm which, given a directed graph G$G$ with n$n$ vertices, decides either that one can add at most βn$\beta n$ new edges to G$G$ so that G$G$ acquires a Hamiltonian circuit or that one cannot add αn$\alpha n$ or fewer new edges to G$G$ so that G$G$ acquires at least e^−f(n)n!$e^{-f\left(n\right)}n!$ Hamiltonian circuits, or both.     

Strongly quasi-Hamiltonian-connected semicomplete multipartite digraphs

A semicomplete multipartite or semicomplete c$c$-partite digraph D$D$ is a biorientation of a c$c$-partite graph. A semicomplete multipartite digraph D$D$ is called strongly quasi-Hamiltonian-connected, if for any two distinct vertices x$x$ and y$y$ of D$D$, there is a path P$P$ from x$x$ to y$y$ such that P$P$ contains at least one vertex from each partite set of D$D$.     

A combinatorial proof of the skew K-saturation theorem

We give a combinatorial proof of the skew version of the K-saturation theorem. More precisely, for any positive integer k$k$, we give an explicit injection from the set of skew semistandard Young tableaux with skew shape kλ/kμ$k\lambda /k\mu$ and type kν$k\nu$, to the set of skew semistandard Young tableaux of shape λ/μ$\lambda /\mu$ and type ν$\nu$.     

On the convergence of hybrid polynomial approximation to higher derivatives of rational curves

In this paper, we derive the bounds on the magnitude of l  th (l=2,3)$(l=2,3)$ order derivatives of rational Bézier curves, estimate the error, in the _L∞$L_{\infty }$ norm sense, for the hybrid polynomial approximation of the l  th (l=1,2,3)$(l=1,2,3)$ order derivatives of rational Bézier curves. We then prove that when the hybrid polynomial approximation converges to a given rational Bézier curve, the l  th (l=1,2,3)$(l=1,2,3)$ derivatives of the hybrid polynomial approximation curve also uniformly converge to the corresponding derivatives of the rational curve. These results are useful for designing simpler algorithms for computing tangent vector, curvature vector and torsion vector of rational Bézier curves.     

Newton’s method and high-order algorithms for the nth root computation

Two modifications of Newton’s method to accelerate the convergence of the n$n$th root computation of a strictly positive real number are revisited. Both modifications lead to methods with prefixed order of convergence p∈N,p≥2$p\in \mathbb{N},p\ge 2$. We consider affine combinations of the two modified p$p$th-order methods which lead to a family of methods of order p$p$ with arbitrarily small asymptotic constants. Moreover the methods are of order p+1$p+1$ for some specific values of a parameter. Then we consider affine combinations of the three methods of order p+1$p+1$ to get methods of order p+1$p+1$ again with arbitrarily small asymptotic constants. The methods can be of order p+2$p+2$ with arbitrarily small asymptotic constants, and also of order p+3$p+3$ for some specific values of the parameters of the affine combination. It is shown that infinitely many p$p$th-order methods exist for the n$n$th root computation of a strictly positive real number for any p≥3$p\ge 3$.     

Approximate martingale estimating functions for stochastic differential equations with small noises

An approximate martingale estimating function with an eigenfunction is proposed for an estimation problem about an unknown drift parameter for a one-dimensional diffusion process with small perturbed parameter ε$\epsilon$ from discrete time observations at n$n$ regularly spaced time points k/n$k/n$, k=0,1,…,n$k=0,1,\dots ,n$. We show asymptotic efficiency of an M$M$-estimator derived from the approximate martingale estimating function as ε→0$\epsilon \to 0$ and n→∞$n\to \infty$ simultaneously.     

Some decomposition results for a class of vacation queues

We analyze the MAP/PH/1 vacation system at arbitrary times using the matrix-analytic method, and obtain decomposition results for the R$R$ and G$G$ matrices. The decomposition results reduce the amount of computational effort needed to obtain these matrices. The results for the G$G$ matrix are extended to the BMAP/PH/1 system. We also show that in the case of the Geo/PH/1 and M/PH/1 systems with PH vacations both the G$G$ and R$R$ matrices can be obtained explicitly.     

A new method for computing Moore–Penrose inverse matrices

The Moore–Penrose inverse of an arbitrary matrix (including singular and rectangular) has many applications in statistics, prediction theory, control system analysis, curve fitting and numerical analysis. In this paper, an algorithm based on the conjugate Gram–Schmidt process and the Moore–Penrose inverse of partitioned matrices is proposed for computing the pseudoinverse of an m×n$m\times n$ real matrix A$A$ with m≥n$m\ge n$ and rank r≤n$r\le n$. Numerical experiments show that the resulting pseudoinverse matrix is reasonably accurate and its computation time is significantly less than that of pseudoinverses obtained by the other methods for large sparse matrices.     

Light-likeness of boundaries of extremal surfaces of mixed type in physical space–times

In this paper, we prove the light-likeness of boundaries of smooth extremal surfaces of mixed type in general physical space–time R¹⁺ⁿ$R^{1+n}$(n>1)$(n>1)$, in particular we improve Gu's theorem on the light-likeness of boundaries of extremal surfaces in R¹⁺²$R^{1+2}$ and prove the light-likeness of boundaries of smooth extremal surfaces of mixed type in general physical space–times. As a consequence, we show that a curve moving in a physical space–time keeps its like-property and the boundary only exists when its world sheet at the initial time has light-like points. This implies that any extremal surface of mixed type is generated by an “initial curve of mixed type”.     

Critical edges for the assignment problem: Complexity and exact resolution

This paper investigates two problems related to the determination of critical edges for the minimum cost assignment problem. Given a complete bipartite balanced graph with n$n$ vertices on each part and with costs on its edges, k$k$Most Vital Edges Assignment consists of determining a set of k$k$ edges whose removal results in the largest increase in the cost of a minimum cost assignment. A dual problem, Min Edge Blocker Assignment, consists of removing a subset of edges of minimum cardinality such that the cost of a minimum cost assignment in the remaining graph is larger than or equal to a specified threshold. We show that k$k$Most Vital Edges Assignment is NP$NP$-hard to approximate within a factor c<2$c<2$ and Min Edge Blocker Assignment is NP$NP$-hard to approximate within a factor 1.36$1.36$. We also provide an exact algorithm for k$k$Most Vital Edges Assignment that runs in O(n^k+2)$O\left(n^{k+2}\right)$. This algorithm can also be used to solve exactly Min Edge Blocker Assignment.