Watermark design based on Steiner triple systems

Constructing a set of watermarks of a specific structure may be one requirement for robust watermarking. This study aims to use the structure of Steiner triple systems to generate new watermarks. That is, the new watermark is a Steiner triple system built by using two smaller ones. The structure properties are examined to recognize watermarks at the receiver site. The main advantage is no information other than the mathematical structure has to be known for watermark recognition.Theoretical proof is given to verify the proposed watermark design method, and the experiment is conducted to confirm the theoretical behavior of the generated watermarks under random noise.     

Implicitization,parameterization and singularity computation of Steiner surfaces using moving surfaces

A Steiner surface is a quadratically parameterizable surface without base points. To make Steiner surfaces more applicable in Computer Aided Geometric Design and Geometric Modeling, this paper discusses implicitization, parameterization and singularity computation of Steiner surfaces using the moving surface technique. For implicitization, we prove that there exist two linearly independent moving planes with total degree one in the parametric variables. From this fact, the implicit equation of a Steiner surface can be expressed as a 3×3 determinant. The inversion formula and singularities for the Steiner surface can also be easily computed from the moving planes. For parameterization, we first compute the singularities of a Steiner surface in implicit form. Based on the singularities, we can find some special moving planes, from which a quadratic parameterization of the Steiner surface can be retrieved.     

Generalized Preparata codes and 2-resolvable Steiner quadruple systems

We consider generalized Preparata codes with a noncommutative group operation. These codes are shown to induce new partitions of Hamming codes into cosets of these Preparata codes. The constructed partitions induce 2-resolvable Steiner quadruple systems S(n, 4, 3) (i.e., systems S(n, 4, 3) that can be partitioned into disjoint Steiner systems S(n, 4, 2)). The obtained partitions of systems S(n, 4, 3) into systems S(n, 4, 2) are not equivalent to such partitions previously known.     

Conflict-avoiding codes and cyclic triple systems

The paper deals with the problem of constructing a code of the maximum possible cardinality consisting of binary vectors of length n and Hamming weight 3 and having the following property: any 3 × n matrix whose rows are cyclic shifts of three different code vectors contains a 3 × 3 permutation matrix as a submatrix. This property (in the special case w = 3) characterizes conflict-avoiding codes of length n for w active users, introduced in [1]. Using such codes in channels with asynchronous multiple access allows each of w active users to transmit a data packet successfully in one of w attempts during n time slots without collisions with other active users. An upper bound on the maximum cardinality of a conflict-avoiding code of length n with w = 3 is proved, and constructions of optimal codes achieving this bound are given. In particular, there are found conflict-avoiding codes for w = 3 which have much more vectors than codes of the same length obtained from cyclic Steiner triple systems by choosing a representative in each cyclic class.     

Tilings and Submonoids of Metabelian Groups

In this paper we show that membership in finitely generated submonoids is undecidable for the free metabelian group of rank 2 and for the wreath product ℤ≀(ℤ×ℤ). We also show that subsemimodule membership is undecidable for finite rank free (ℤ×ℤ)-modules. The proof involves an encoding of Turing machines via tilings. We also show that rational subset membership is undecidable for two-dimensional lamplighter groups.     

Alternative Tilings for Improved Surface Area Estimates by Local Counting Algorithms

In this paper, we first review local counting methods for perimeter estimation of piecewise smooth binary figures on square, hexagonal, and triangular grids. We verify that better perimeter estimates, using local counting algorithms, can be obtained using hexagonal or triangular grids. We then compare surface area estimates using local counting techniques for binary three-dimensional volumes under the three semi-regular polyhedral tilings: the cubic, truncated octahedral, and rhombic dodecahedral tilings. It is shown that for surfaces of random orientation with a uniform distribution, the expected error of surface area estimates is smaller for the truncated octahedral and rhombic dodecahedral tilings than for the standard cubic or rectangular prism tilings of space. Additional properties of these tessellations are reviewed and potential applications of better surface area estimates are discussed.     

Non-full-rank Steiner quadruple systems S(v, 4, 3)

All different Steiner systems S(2 ^m , 4, 3) of order 2 ^m and rank 2 ^m ? m ? 1 + s over \(\mathbb{F}_2\) , where 0 ≤ s ≤ m ? 1, are constructed. The number of different systems S(2 ^m , 4, 3) whose incident matrices are orthogonal to a fixed code is obtained. A connection between the number of different Steiner systems and of different Latin cubes is described.     

Chair Tilings非周期艺术图案的生成

在Chair tilings结构的基础上构造出新的函数来生成彩色非周期图案,其原胞具有丰富的图形结构,为计算机实现非周期拼砌提供了新方法．     

On the location of Steiner points in uniformly-oriented Steiner trees

We give a fundamental result on the location of Steiner points for Steiner minimum trees in uniform orientation metrics. As a corollary we obtain a linear time algorithm for constructing a Steiner minimum tree for a given full topology when the number of uniform orientations is λ=3m,m?1.     

基于三Ⅰ算法的模糊系统的响应能力

探讨模糊系统的函数逼近能力是模糊系统理论研究的一个重要的课题.本文首次讨论了在两种推理规则情形下由三Ⅰ支持度算法和模糊熵三Ⅰ算法设计的模糊系统的响应能力.针对三Ⅰ支持度算法,分别就正则蕴涵算子和11个具体的模糊蕴涵算子,考察了相应模糊系统的响应能力,讨论了基于模糊熵三Ⅰ算法和三Ⅰ算法设计的模糊系统的响应函数之间的关系....     

A bottleneck Steiner tree based multi-objective location model and intelligent optimization of emergency logistics systems

Logistics networks could be very fragile in a global environment due to unexpected emergencies such as earthquakes, tsunamis and terrorists attacks. Therefore, the research on emergency logistics systems is extremely significant. The dynamic changes, quick responses and unpredictable events are main features of the location problems in emergency logistics systems, which make them quite different from the traditional logistics networks. The previous single-objective location models and solution algorithms do not capture the new characteristics that arise from the emergency logistics systems. This paper first proposes a new node-weighted bottleneck Steiner tree based multi-objective location optimization model for the emergency logistics systems. Then, a cellular stochastic diffusion search based intelligent algorithm is introduced to solve the proposed model. Under different emergent scenarios, several examples are used to illustrate the application of the proposed model. Numerical experiments show that the proposed approach is effective and efficient for solving the location problem of emergency logistics systems.     

Expansion of Linear Steiner Trees

A Steiner tree T on a given set of points A is called linear if all Steiner points, including those collapsing into their adjacent given points, lie on one path referred to as its trunk. Suppose A is a simple polygonal line. Roughly speaking, T is similar to A if its trunk turns right or left when A does. In this paper we prove that A can be expanded to another polygonal line, and T can be constructed in linear time using this expansion method. Received January 15, 1995; revised November 19, 1995, and February 3, 1996.     

Steiner Tree问题的研究进展

Steiner树问题是经典的NP难解问题,在计算机网络布局、电路设计以及生物网络等领域都有很多应用。随着参数计算理论的发展,已经证明了无向图和有向图中的Steiner树问题都是固定参数可解的(FPT)。介绍了无向图和有向图中Steiner树问题的近似算法和参数算法,分析了一些特殊Steiner树问题的研究现状,还讨论了顶点加权Steiner树问题的研究进展。最后,提出了该问题的进一步研究方向。     

Moving sliding surfaces for high-order variable structure systems

A moving sliding surface(MSS) was proposed earlier for the second-order variable structure controlsystem (VSCS). The MSS was designed to pass arbitrary initial conditions, and subsequently moved towards a predetermined sliding surface by rotating and/or shifting. This methodology led to fast and robust control responses of the second-order VSCS, especially in a reaching phase. However, the moving algorithm of the MSS was too complicated to be employed for the high-order VSCS. To resolve this problem, a new moving algorithm based on fuzzy theory is proposed in this paper. For the generalization of the MSS, the conditions for rotating or shifting are firstly investigated. Then the fuzzy algorithm is formulated by adopting the values of the surface function and the total discontinuity gain as input variables and the variation of the surface function as output variable. The efficiency of the proposed moving algorithm is illustrated by applying it to the position control problem of an electrohydraulic servomechanism.     

Simulating continuous fuzzy systems for fuzzy solution surfaces

Our approach to simulation of a fuzzy ODE system is to evaluate the system with triangular fuzzy parameters, evaluating at the left/vertex/right supports and values in between. Solutions are presented as a graph(s) of the variable(s) of interest, with respect to time. With multiple fuzzy parameters, a solution graph is likely to become overloaded with superfluous information. Because of the cost of processing and plotting the superfluous information, critical support values may be skipped. We implement a reduction algorithm for determining solution boundaries, as trajectories are computed. Keeping aware of membership values, quantization considerations, and solution neighborhoods, we are able to collect a fraction of the data collected by brute force methods, and yet provide better coverage of fuzzy parameters. Three dimensional fuzzy solution trajectories are the second improvement we investigate. By including membership computation in our simulations, we produce fuzzy solution surface boundaries. These surfaces enclose the possible solution space. To make this process manageable, we combine this with boundary determination. In this paper we describe our method and present 3D solutions of two classical systems of ODE.     

Technologies for implicit surfaces sampling with particle systems

Point-based surface has been widely used in computer graphics for modeling,animation,visualization,simulation of liquid and so on.Furthermore,particle-based approach can distribute the surface sampling points and control its parameters according to the needs of the application.In this paper,we examine several kinds of algorithms presented over the last decades,with the main focus on particle sampling technologies for implicit surface.Therefore,we classify various algorithms into categories,describe main ideas behind each categories,and compare the advantages and shortcomings of the algorithms in each category.     

Steiner Tree问题的研究进展

Steiner树问题是经典的NP难解问题,在计算机网络布局、电路设计以及生物网络等领域都有很多应用.随着参数计算理论的发展,已经证明了无向图和有向图中的Steiner树问题都是固定参数可解的(FPT).介绍了无向图和有向图中Steiner树问题的近似算法和参数算法,分析了一些特殊Steiner树问题的研究现状,还讨论了顶点加权Steiner树问题的研究进展.最后,提出了该问题的进一步研究方向.     

The multi-weighted Steiner tree problem: A reformulation by intersection

We propose a new formulation for the multi-weighted Steiner tree (MWST) problem. This formulation is based on the fact that a previously proposed formulation for the problem is non-symmetric in the sense that the corresponding linear programming relaxation bounds depend on the node selected as a root of the tree. The new formulation (the reformulation by intersection) is obtained by intersecting the feasible sets of the models corresponding to each possible root selection for the underlying directed problem. Theoretical results will show that the linear programming relaxation of the new formulation dominates the linear programming relaxation of each of the rooted formulations and is comparable with the linear programming bounds of the best formulation known for the problem. A Lagrangean relaxation scheme derived from the new formulation is also proposed and tested, with quite favourable results, on instances with up to 500 nodes and 5000 edges.