Minimal simple closed 18-surfaces and a topological preservation of 3D surfaces

The aim of this paper is to investigate a map which preserves digital topological properties of a digital 3D surface, such as the topological number, digital k-contractibility and so on. Furthermore, the two types of minimal simple closed 18-surfaces MSS₁₈ and are established in Z³ in relation with 18-contractibility, which are shown to be different from each other up to digital 18-homotopy. Moreover, it is proved that MSS₁₈ is the minimal simple closed 18-surface without 18-contractibility and is the minimal Malgouyres’ simple closed 18-surface with 18-contractibility. Finally, we show that a digital (k₀,k₁)-homeomorphism preserves a simple k₀-surface to a simple k₁-surface and vice versa.     

The interval-merging problem

A closed interval is an ordered pair of real numbers [x, y], with x ? y. The interval [x, y] represents the set {i ∈ R∣x ? i ? y}. Given a set of closed intervals I={[a₁,b₁],[a₂,b₂],…,[a_k,b_k]}, the Interval-Merging Problem is to find a minimum-cardinality set of intervals M(I)={[x₁,y₁],[x₂,y₂],…,[x_j,y_j]}, j ? k, such that the real numbers represented by equal those represented by . In this paper, we show the problem can be solved in O(d log d) sequential time, and in O(log d) parallel time using O(d) processors on an EREW PRAM, where d is the number of the endpoints of I. Moreover, if the input is given as a set of sorted endpoints, then the problem can be solved in O(d) sequential time, and in O(log d) parallel time using O(d/log d) processors on an EREW PRAM.     

Fully Smoothed ℓ 1-TV Models: Bounds for the Minimizers and Parameter Choice

We consider a class of convex functionals that can be seen as $\mathcal{C}^{1}$ smooth approximations of the ? ₁-TV model. The minimizers of such functionals were shown to exhibit a qualitatively different behavior compared to the nonsmooth ? ₁-TV model (Nikolova et al. in Exact histogram specification for digital images using a variational approach, 2012). Here we focus on the way the parameters involved in these functionals determine the features of the minimizers  $\hat{u}$ . We give explicit relationships between the minimizers and these parameters. Given an input digital image f, we prove that the error $\|\hat{u}- f\| _{\infty}$ obeys $b-\varepsilon\leq\|\hat{u}-f\|_{\infty}\leq b$ where b is a constant independent of the input image. Further we can set the parameters so that ε>0 is arbitrarily close to zero. More precisely, we exhibit explicit formulae relating the model parameters, the input image f and the values b and ε. Conversely, we can fix the parameter values so that the error $\|\hat{u}- f\|_{\infty}$ meets some prescribed b,ε. All theoretical results are confirmed using numerical tests on natural digital images of different sizes with disparate content and quality.     

Winding and Euler numbers for 2D and 3D digital images

New algorithms for computing the Euler number of a 3D digital image S are given, based on smoothing the image to a differentiable object and applying theorems of differential geometry and algebraic topology. They run in O(n) time, where n is the number of object elements of S with neighbors not in S. The basic idea is general and easily extended to images defined by other means, such as a hierarchical data structure or a union of isothetic (hyper) rectangles.     

Two-dimensional array codes correcting rectangular burst errors

Two-dimensional array codes correcting rectangular burst errors are considered. We give a construction and examples of linear two-dimensional array codes correcting rectangular burst errors of size b ₁ × b ₂ with minimum redundancy r = 2b ₁ b ₂. We present constructions of cyclic two-dimensional array codes correcting phased and arbitrary rectangular burst errors; their encoding and decoding algorithms are also given. A class of cyclic two-dimensional array codes correcting rectangular burst errors with asymptotically minimal redundancy is described. We construct a class of linear two-dimensional array codes correcting cyclic rectangular b ₁ × b ₂ burst errors with asymptotic excess redundancy $\tilde r_C (b_1 ,b_2 ) = 2b_1 b_2 - 3$ .     

Effects of topological changes in microchannel geometries on the asymmetric breakup of a droplet

Passive asymmetric breakups of a droplet could be done in many microchannels of various geometries. In order to study the effects of different geometries on the asymmetric breakup of a droplet, four types of asymmetric microchannels with the topological equivalence of geometry are designed, which are T-90, Y-120, Y-150, and I-180 microchannels. A three-dimensional volume of fluid multiphase model is employed to investigate the asymmetric rheological behaviors of a droplet numerically. Three regimes of rheological behaviors as a function of the capillary numbers Ca and the asymmetries As defined by As = (b1 ? b2)/(b1 + b2) (where b1 and b2 are the widths of two asymmetric sidearms) have been observed. A power law model based on three major factors (Ca, As and the initial volume ratio r ₀) is employed to describe the volume ratio of two daughter droplets. The analysis of pressure fields shows that the pressure gradient inside the droplet is one of the major factors causing the droplet translation during its asymmetric breakup. Besides the above similarities among various microchannels, the asymmetric breakup in them also have some slight differences as various geometries have different enhancement or constraint effects on the translation of the droplet and the cutting action of flows. It is disclosed that I-180 microchannel has the smallest critical capillary number, the shortest splitting time, and is hardest to generate satellite droplets.     

ASM: An adaptive simplification method for 3D point-based models

Due to the popularity of computer games and computer-animated movies, 3D models are fast becoming an important element in multimedia applications. In addition to the conventional polygonal representation for these models, the direct adoption of the original scanned 3D point set for model representation is recently gaining more and more attention due to the possibility of bypassing the time consuming mesh construction stage, and various approaches have been proposed for directly processing point-based models. In particular, the design of a simplification approach which can be directly applied to 3D point-based models to reduce their size is important for applications such as 3D model transmission and archival. Given a point-based 3D model which is defined by a point set P () and a desired reduced number of output samples n^s, the simplification approach finds a point set P_s which (i) satisfies |P_s|=n^s (|P_s| being the cardinality of P_s) and (ii) minimizes the difference of the corresponding surface S_s (defined by P_s) and the original surface S (defined by P). Although a number of previous approaches has been proposed for simplification, most of them (i) do not focus on point-based 3D models, (ii) do not consider efficiency, quality and generality together and (iii) do not consider the distribution of the output samples. In this paper, we propose an Adaptive Simplification Method (ASM) which is an efficient technique for simplifying point-based complex 3D models. Specifically, the ASM consists of three parts: a hierarchical cluster tree structure, the specification of simplification criteria and an optimization process. The ASM achieves a low computation time by clustering the points locally based on the preservation of geometric characteristics. We analyze the performance of the ASM and show that it outperforms most of the current state-of-the-art methods in terms of efficiency, quality and generality.     

Counting networks with arbitrary fan-out

Summary It is shown that an acyclic smoothing network (and hence counting network) with fan-outn cannot be constructed from balancers of fan-outb ₁,...,b _k , if there exists a prime factorp ofn, such thatp does not divideb _i , for alli, 1ik. This holds regardless of the depth, fan-in or size of the network, as long as they are finite. On the positive side, a simple construction ofcyclic counting networks with fan-outn, for arbitraryn, is presented. An acyclic counting network with fan-in and fan-outp2 ^k , for any integerk0, is constructed out of 2-balancers andp-balancers. Eran Aharonson received the B.A. and M.Sc. degrees in Computer Science from the Technion, Israel Institute of Technology (Haifa, Israel) in 1989 and 1992, respectively. He is currently vice president for research and development at ART-Advanced Recognition Technolgies Ltd., a company dedicated to handwriting and voice recognition. His general research interests are distributed computation, theoretical computer science and pattern recognition. Hagit Attiya received the B.Sc. degree in Mathematics and Computer Science from the Hebrew University of Jerusalem, in 1981, the M.Sc. and Ph.D. degrees in Computer Science from the Hebrew University of Jerusalem, in 1983 and 1987, respectively. She is presently a senior lecturer at the department of Computer Science at the Technion, Israel Institute of Technology. Prior to this, she has been a post-doctoral research associate at the Laboratory for Computer Science at M.I.T. Her general research interests are distributed computation and theoretical computer science. More specific interests include fault-tolerance, timing-based and asynchronous algorithms.A preliminary version of this paper appears in proceedings of the3rd Annual ACM-SIAM Symposium on Discrete Algorithms, January 1992, pp. 104–113. This research was supported by Technion V.P.R.-B. and G. Greenberg Research Fund (Ottawa)Supported by Rashi Enterprise graduate fellowship     

Compressed piecewise-circular approximations of 3D curves

We propose a compact approximation scheme for 3D curves. Consider a polygonal curve P, whose n vertices have been generated through adaptive (and nearly minimal) sampling, so that P approximates some original 3D curve, O, within tolerance ε₀. We present a practical and efficient algorithm for computing a continuous 3D curve C that approximates P within tolerance ε₁ and is composed of a chain of m circular arcs, whose end-points coincide with a subset of the vertices of P. We represent C using 5m+3 scalars, which we compress within a carefully selected quantization error ε₂. Empirical results show that our approximation uses a total of less than 7.5n bits, when O is a typical surface/surface intersection and when the error bound ε₁+ε₂ is less than 0.02% of the radius of a minimal sphere around O. For less accurate approximations, the storage size drops further, reaching for instance a total of n bits when ε₁+ε₂ is increased to 3%. The storage cost per vertex is also reduced when ε₀ is decreased to force a tighter fit for smooth curves. As expected, the compression deteriorates for jagged curves with a tight error bound. In any case, our representation of C is always more compact than a polygonal curve that approximate O with the same accuracy. To guarantee a correct fit, we introduce a new error metric for ε₁, which prevents discrepancies between P and C that are not detected by previously proposed Hausdorff or least-square error estimates. We provide the details of the algorithms and of the geometric constructions. We also introduce a conservative speed-up for computing C more efficiently and demonstrate that it is sub-optimal in only 2% of the cases. Finally, we report results on several types of curves and compare them to previously reported polygonal approximations, observing compression ratios that vary between 15:1 and 36:1.     

No-Three-in-Line-in-3D

The no-three-in-line problem, introduced by Dudeney in 1917, asks for the maximum number of points in the n × n grid with no three points collinear. Erdos proved that the answer is Θ(n). We consider the analogous problem in three dimensions, and prove that the maximum number of points in the n × n × n grid with no three collinear is Θ(n²). This result is generalised by the notion of a 3D drawing of a graph. Here each vertex is represented by a distinct gridpoint in , such that the line-segment representing each edge does not intersect any vertex, except for its own endpoints. Note that edges may cross. A 3D drawing of a complete graph K_n is nothing more than a set of n gridpoints with no three collinear. A slight generalisation of our first result is that the minimum volume for a 3D drawing of K_n is Θ(n^3/2). This compares favourably with Θ(n³) when edges are not allowed to cross. Generalising the construction for K_n, we prove that every k-colourable graph on n vertices has a 3D drawing with volume, which is optimal for the k-partite Turan graph.     

An algorithm for division of powerseries

An algorithm is given to compute a solution (b ₀, ...,b _n) of $$\sum\limits_0^n {a_i t^i } \sum\limits_0^n {b_i t^i } \equiv \sum\limits_0^n {c_i t^i } (t^{n + 1} )$$ froma ₀, ..., a_n, c₀, ..., c_n. It needs less than 7n multiplications, where multiplications with a skalar from an infinite subfield are not counted.     

On the subword complexity of m-free D0L languages

A word is called m-free (m ? 2) if it does not contain a subword of the form x^m where x is a nonempty word. A language is called m-free if it consists of m-free words only. The subword complexity of a language K, denoted π_K, is a function of positive integers which to each positive integer n assigns the number of different subwords of length n occuring in words of K. It is known that if a D0L language K is m-free for some m ? 2, then, for all n, π_K(n) ? qn log₂n for some positive integer q. We demonstrate that there exists a 3-free D0L language K on three letters such that, for all n ? n₀, π_K(n) ? rn log₂n for some positive real r and a positive integer n₀. We also demonstrate that if m ? 3 and K is an m-free D0L language on two letters, then, for all n, π_K(n) ? pn for some positive integer p.     

Comparison among digital fundamental groups and its applications

The notion of digital fundamental group was originated by Khalimsky [E. Khalimsky, Motion, deformation, and homotopy in finite spaces, Proc. IEEE Int. Conf. Syst. Man Cybernet. (1987) 227-234]. Motivated by this notion, three kinds of digital k-homotopies as well as the relative k-homotopy were established [R. Ayala, E. Domínguez, A.R. Francés, A. Quintero, Homotopy in digital spaces, Discrete Appl. Math. 125 (1) (2003) 3-24; L. Boxer, A classical construction for the digital fundamental group, J. Math. Imaging Vis. 10 (1999) 51-62; S.E. Han, Connected sum of digital closed surfaces, Inform. Sci. 176 (3) (2006a) 332-348; T.Y. Kong, A digital fundamental group, Comput. Graphics 13 (1989) 159-166; R. Malgouyres, Homotopy in 2-dimensional digital images, Theor. Comput. Sci. 230 (2000) 221-233]. These four notions contributed to the development of three kinds of k-fundamental groups of a digital image (X,k). One was established by Kong [Kong, 1989] and Malgouyres [Malgouyres, 2000], and we denote by this digital fundamental group. Another was developed by Boxer [Boxer, 1999] and extended by Han [Han, 2006a; S.E. Han, Discrete Homotopy of a closed k-surface, LNCS 4040, Springer-Verlag, Berlin, 2006b, pp. 214-225; S.E. Han, Equivalent (k₀,k₁)-covering and generalized digital lifting, Inform. Sci. 178 (2) (2008) 550-561] by using both the k-homotopic thinning [Han, 2006b; S.E. Han, Remarks on digital k-homotopy equivalence, Honam Math. J. 29 (1) (2007) 101-118] and Han’s digital covering theory [S.E. Han, Digital coverings and their applications, J. Appl. Math. Comput. 18 (1-2) (2005) 487-495; Han, 2006b], which is denoted as in this paper. The other was established by Ayala et al. by using the framework of a multilevel architecture [Ayala, 2003]. Since each of these digital k-fundamental groups has an intrinsic feature of its own and its usages depend on the situation. This study is focused on the first two notions, and , and intended to show the strong merits of in relation to the classification of digital images.     

Topological Repairing of 3D Digital Images

We present here a new randomized algorithm for repairing the topology of objects represented by 3D binary digital images. By “repairing the topology”, we mean a systematic way of modifying a given binary image in order to produce a similar binary image which is guaranteed to be well-composed. A 3D binary digital image is said to be well-composed if, and only if, the square faces shared by background and foreground voxels form a 2D manifold. Well-composed images enjoy some special properties which can make such images very desirable in practical applications. For instance, well-known algorithms for extracting surfaces from and thinning binary images can be simplified and optimized for speed if the input image is assumed to be well-composed. Furthermore, some algorithms for computing surface curvature and extracting adaptive triangulated surfaces, directly from the binary data, can only be applied to well-composed images. Finally, we introduce an extension of the aforementioned algorithm to repairing 3D digital multivalued images. Such an algorithm finds application in repairing segmented images resulting from multi-object segmentations of other 3D digital multivalued images.

ARCADE: A prediction method for nominal variables

The main problem considered in this paper consists of binarizing categorical (nominal) attributes having a very large number of values (20⁴ in our application). A small number of relevant binary attributes are gathered from each initial attribute. Let us suppose that we want to binarize a categorical attribute v with L values, where L is large or very large. The total number of binary attributes that can be extracted from v is 2^L−1− 1, which in the case of a large L is prohibitive. Our idea is to select only those binary attributes that are predictive; and these shall constitute a small fraction of all possible binary attributes. In order to do this, the significant idea consists in grouping the L values of a categorical attribute by means of an hierarchical clustering method. To do so, we need to define a similarity between values, which is associated with their predictive power. By clustering the L values into a small number of clusters (J), we define a new categorical attribute with only J values. The hierarchical clustering method used by us, AVL, allows to choose a significant value for J. Now, we could consider using all the 2^L−1− 1 binary attributes associated with this new categorical attribute. Nevertheless, the J values are tree-structured, because we have used a hierarchical clustering method. We profit from this, and consider only about 2 × J binary attributes. If L is extremely large, for complexity and statistical reasons, we might not be able to apply a clustering algorithm directly. In this case, we start by “factorizing” v into a pair (v², v²), each one with about √L(v) values. For a simple example, consider an attribute v with only four values m₁,m₂, m₃,m₄. Obviously, in this example, there is no need to factorize the set of values of v, because it has a very small number of values. Nevertheless, for illustration purposes, v could be decomposed (factorized) into 2 attributes with only two values each; the correspondence between the values of v and (v², v²) would be     

18.

Applications of complete discrimination system for polynomial for classifications of traveling wave solutions to nonlinear differential equations     

Cheng-shi Liu 《Computer Physics Communications》2010,181(2):317-2276

If a partial differential equation is reduced to an ordinary differential equation in the form u^′(ξ)=G(u,θ₁,…,θm) under the traveling wave transformation, where θ₁,…,θm are parameters, its solutions can be written as an integral form . Therefore, the key steps are to determine the parameters' scopes and to solve the corresponding integral. When G is related to a polynomial, a mathematical tool named complete discrimination system for polynomial is applied to this problem so that the parameter's scopes can be determined easily. The complete discrimination system for polynomial is a natural generalization of the discrimination △=b²−4ac of the second degree polynomial ax²+bx+c. For example, the complete discrimination system for the third degree polynomial F(w)=w³+d₂w²+d₁w+d₀ is given by and . In the paper, we give some new applications of the complete discrimination system for polynomial, that is, we give the classifications of traveling wave solutions to some nonlinear differential equations through solving the corresponding integrals. In finally, as a result, we give a partial answer to a problem on Fan's expansion method.     

19.

Effective condition number and its applications     

Zi-Cai Li  Hung-Tsai Huang  Jeng-Tzong Chen  Yimin Wei 《Computing》2010,89(1-2):87-112

Consider the over-determined system Fx = b where ${{\bf F}\in\mathcal{R}^{m \times n}, m \geq n}$ and rank (F) = r ≤ n, the effective condition number is defined by ${{\rm Cond_{-}eff }= \frac {\|{\bf b}\|}{\sigma_r\|{\bf x}\|}}$ , where the singular values of F are given as σ _max = σ ₁ ≥ σ ₂ ≥ . . . ≥ σ _r > 0 and σ _r+1 = . . . = σ _n = 0. For the general perturbed system (A+ΔA)(x+Δx) = b+Δb involving both ΔA and Δb, the new error bounds pertinent to Cond_eff are derived. Next, we apply the effective condition number to the solutions of Motz’s problem by the collocation Trefftz methods (CTM). Motz’s problem is the benchmark of singularity problems. We choose the general particular solutions ${v_L = \sum\nolimits_{k=0}^L d_k (\frac {r}{R_p})^{k+\frac 12}}$ ${{\rm cos}(k +\frac 12)\theta}$ with a radius parameter R _p . The CTM is used to seek the coefficients d _i by satisfying the boundary conditions only. Based on the new effective condition number, the optimal parameter R _p = 1 is found. which is completely in accordance with the numerical results. However, if based on the traditional condition number Cond, the optimal choice of R _p is misleading. Under the optimal choice R _p = 1, the Cond grows exponentially as L increases, but Cond_eff is only linear. The smaller effective condition number explains well the very accurate solutions obtained. The error analysis in [14,15] and the stability analysis in this paper grant the CTM to become the most efficient and competent boundary method.     

20.

Modifikationen des Pollard-Algorithmus     

Dr. R. Gold  J. Sattler 《Computing》1983,30(1):77-89

The factorization algorithm of Pollard generates a sequence in ? _n by $$x_0 : = 2;x_{i + 1} : = x_i^2 - 1(\bmod n),i = 1,2,3,...$$ wheren denotes the integer to be factored. The algorithm finds an factorp ofn within \(0\left( {\sqrt p } \right)\) macrosteps (=multiplications/divisions in ? _n ) on average. An empirical analysis of the Pollard algorithm using modified sequences $$x_{i + 1} = b \cdot x_i^\alpha + c(\bmod n),i = 1,2,...$$ withx ₀,b,c,α∈? and α≥2 shows, that a factorp ofn under the assumption gcd (α,p-1)≠1 now is found within $$0\left( {\sqrt {\frac{p}{{ged(\alpha ,p - 1}}} } \right)$$ macrosteps on average.     

Applications of complete discrimination system for polynomial for classifications of traveling wave solutions to nonlinear differential equations

If a partial differential equation is reduced to an ordinary differential equation in the form u^′(ξ)=G(u,θ₁,…,θm) under the traveling wave transformation, where θ₁,…,θm are parameters, its solutions can be written as an integral form . Therefore, the key steps are to determine the parameters' scopes and to solve the corresponding integral. When G is related to a polynomial, a mathematical tool named complete discrimination system for polynomial is applied to this problem so that the parameter's scopes can be determined easily. The complete discrimination system for polynomial is a natural generalization of the discrimination △=b²−4ac of the second degree polynomial ax²+bx+c. For example, the complete discrimination system for the third degree polynomial F(w)=w³+d₂w²+d₁w+d₀ is given by and . In the paper, we give some new applications of the complete discrimination system for polynomial, that is, we give the classifications of traveling wave solutions to some nonlinear differential equations through solving the corresponding integrals. In finally, as a result, we give a partial answer to a problem on Fan's expansion method.     

Effective condition number and its applications

Consider the over-determined system Fx = b where ${{\bf F}\in\mathcal{R}^{m \times n}, m \geq n}$ and rank (F) = r ≤ n, the effective condition number is defined by ${{\rm Cond_{-}eff }= \frac {\|{\bf b}\|}{\sigma_r\|{\bf x}\|}}$ , where the singular values of F are given as σ _max = σ ₁ ≥ σ ₂ ≥ . . . ≥ σ _r > 0 and σ _r+1 = . . . = σ _n = 0. For the general perturbed system (A+ΔA)(x+Δx) = b+Δb involving both ΔA and Δb, the new error bounds pertinent to Cond_eff are derived. Next, we apply the effective condition number to the solutions of Motz’s problem by the collocation Trefftz methods (CTM). Motz’s problem is the benchmark of singularity problems. We choose the general particular solutions ${v_L = \sum\nolimits_{k=0}^L d_k (\frac {r}{R_p})^{k+\frac 12}}$ ${{\rm cos}(k +\frac 12)\theta}$ with a radius parameter R _p . The CTM is used to seek the coefficients d _i by satisfying the boundary conditions only. Based on the new effective condition number, the optimal parameter R _p = 1 is found. which is completely in accordance with the numerical results. However, if based on the traditional condition number Cond, the optimal choice of R _p is misleading. Under the optimal choice R _p = 1, the Cond grows exponentially as L increases, but Cond_eff is only linear. The smaller effective condition number explains well the very accurate solutions obtained. The error analysis in [14,15] and the stability analysis in this paper grant the CTM to become the most efficient and competent boundary method.     

Modifikationen des Pollard-Algorithmus

The factorization algorithm of Pollard generates a sequence in ? _n by $$x_0 : = 2;x_{i + 1} : = x_i^2 - 1(\bmod n),i = 1,2,3,...$$ wheren denotes the integer to be factored. The algorithm finds an factorp ofn within \(0\left( {\sqrt p } \right)\) macrosteps (=multiplications/divisions in ? _n ) on average. An empirical analysis of the Pollard algorithm using modified sequences $$x_{i + 1} = b \cdot x_i^\alpha + c(\bmod n),i = 1,2,...$$ withx ₀,b,c,α∈? and α≥2 shows, that a factorp ofn under the assumption gcd (α,p-1)≠1 now is found within $$0\left( {\sqrt {\frac{p}{{ged(\alpha ,p - 1}}} } \right)$$ macrosteps on average.