A recursive sweep-plane algorithm,determining all cells of a finite division of Rd

“Sweep-plane” algorithms seem to become more and more important for the solution of certain geometrical problems. We present an algorithm of this kind that enumerates the cells of all dimensions into whichR ^d is partitioned by a finite set of hyperplanesF _i ⁰ . A plane sweeping through space (remaining parallel to itself) finds new cells each time it includes an intersection of someF _i ⁰ (normally a point). An analysis of the intersection-properties allows the construction of an algorithm recursive with respect to the dimension of space. Full generality has been one of our main objectives.     

基于层叠处理的多级自适应WOS滤波器

基于层叠处理的ＬＰ算法求解最优非线性滤波 缺陷在于：⑴必须掌握信号和噪声的先验统计知识,⑵计算量随滤波窗增大呈超指数增加,根据层叠滤波器理论,所有ＷＯＳ滤波器正布尔函数都是线性可分离的,在此基础上,提出了一种多级自适应ＷＯＳ层叠滤波器,从有效地克服了传统ＬＰ算法的缺点,它尤其适合于图象处理领域。     

A tree search procedure for the container relocation problem

In the container relocation problem (CRP) n items are given that belong to G different item groups (g=1,…,G). The items are piled up in up to S stacks with a maximum stack height H. A move can either shift one item from the top of a stack to the top of another one (relocation) or pick an item from the top of a stack and entirely remove it (remove). A move of the latter type is only feasible if the group index of the item is minimum compared to all remaining items in all stacks. A move sequence of minimum length has to be determined that removes all items from the stacks. The CRP occurs frequently in container terminals of seaports. It has to be solved when containers, piled up in stacks, need to be transported to a ship or to trucks in a predefined sequence. This article presents a heuristic tree search procedure for the CRP. The procedure is compared to all known solution approaches for the CRP and turns out to be very competitive.     

Average-case analysis of the Modified Harmonic algorithm

In this paper we analyze the average-case performance of the Modified Harmonic algorithm for on-line bin packing. We first analyze the average-case performance for arbitrary distribution of item sizes over (0,1]. This analysis is based on the following result. Letf ₁ andf ₂ be two linear combinations of random variables {N _i } _i=1 ^k where theN _i 's have a joint multinomial distribution for eachn=σ _i=1 ^k ,N _i . LetE(f ₁) ≠ O andE(f ₂)≠ 0. Then lim_{n →}∞E(max(_{f 1},f ₂ ))/n = lim _n →∞ max(E(f ₁),E(f ₂))/n. We then consider the special case when the item sizes are uniformly distributed over (0,1]. For specific values of the parameters, the Modified Harmonic algorithm turns out to be better than the other two linear-time on-line algorithms—Next Fit and Harmonic—in both the worst case as well as the average case. We also obtain optimal values for the parameters of the algorithm from the average-case standpoint. For these values of the parameters, the average-case performance ratio is less than 1.19. This compares well with the performance ratios 1.333. and 1.2865. of the Next Fit algorithm and the Harmonic algorithm, respectively.     

Solving the Euclidean bottleneck matching problem byk-relative neighborhood graphs

Given a set of pointsV in the plane, the Euclidean bottleneck matching problem is to match each point with some other point such that the longest Euclidean distance between matched points, resulting from this matching, is minimized. To solve this problem, we definek-relative neighborhood graphs, (kRNG) which are derived from Toussaint's relative neighborhood graphs (RNG). Two points are calledk-relative neighbors if and only if there are less thank points ofV which are closer to both of the two points than the two points are to each other. AkRNG is an undirected graph (V,E _r ^k ) whereE _r ^k is the set of pairs of points ofV which arek-relative neighbors. We prove that there exists an optimal solution of the Euclidean bottleneck matching problem which is a subset ofE _r ¹⁷ . We also prove that ¦E _r ^k ¦ < 18kn wheren is the number of points in setV. Our algorithm would construct a 17RNG first. This takesO(n ²) time. We then use Gabow and Tarjan's bottleneck maximum cardinality matching algorithm for general graphs whose time-complexity isO((n logn)^0.5 m), wherem is the number of edges in the graph, to solve the bottleneck maximum cardinality matching problem in the 17RNG. This takesO(n ^1.5 log^0.5 n) time. The total time-complexity of our algorithm for the Euclidean bottleneck matching problem isO(n ² +n ^1.5 log^0.5 n).     

Using the first-level cache stack distance histograms to predict multi-level LRU cache misses

For cache analytical modeling, the stack distance theory is widely utilized to predict LRU-cache behaviors. Typically, the stack distance histogram collecting is implemented by profiling memory references. However, the profiled memory references merely reflect instruction fetching and load/store executions, which only represent the memory accesses to first-level (L1) caches. That is why these traces cannot be applied directly to construct stack distance histograms for downstream (L2 and L3) caches.Therefore, this paper proposes a stack distance probability model to extend the stack distance theory to the multi-level LRU cache behavior predictions. The inputs of our model are the L1 cache stack distance histograms and the multi-level LRU cache configurations. The outputs are the L2 and L3 cache stack distance histograms, with which the conflict misses in L2 and L3 caches can be quantified quickly and precisely.15 benchmarks chosen from Mobybench 2.0, Mibench I and Mediabench II are used to evaluate the accuracy of our model. Compared to the simulation results from Gem5 in AtomicSimpleCPU mode, the average absolute error of predicting cache misses in the I/D shared L2 cache is less than 5% while that of estimating the L3 cache misses is less than 7%. Furthermore, contrast to the time overhead of Gem5 AtomicSimpleCPU simulations, our model can speed up the cache miss prediction about x100 on average.     

Passive target detection and tracking from electromagnetic field measurements

This paper presents a novel approach to the localization of moving targets in a complex environment based on the measurement of the perturbations induced by the target presence on an independently‐generated time‐varying electromagnetic field. Field perturbations are measured via a set of sensors deployed over the domain of interest and used to detect and track a possible target by resorting to a particle Bernoulli filter (PBF). To comply with real‐time operation, the PBF works along with an artificial neural network (ANN) model of the environment trained offline via finite elements (FEs). The performance of the proposed algorithm is assessed via simulation experiments.     

A new approach for the voxelization of volumetric CSG graphs

This paper presents a new approach for the voxelization of volumetric scene graphs. The algorithm generates slices of each primitive intended to be voxelized using an FPGA based pixel processor. The Blist representation is used for the volume scene tree which reduces storage requirement for each voxel to the log(H+1) bits. The most important advantage of this voxelization algorithm is that any volume scene tree expression can be evaluated without using any computation or stack. Also the algorithm is not object specific, i.e. the same algorithm can be used for the voxelization of different types of objects (convex and concave objects, polygons, lines and surfaces).     

An algorithm for constructing toric compactifications

The paper puts forward a computer algebra algorithm to calculate parameters of toric compactification of ? ⁿ in which a given smooth toric variety can be embedded as a “skeleton of infinity.” Such a compactification of an affine space extends the well-known decomposition ? _n = ? ⁿ ? ? _n?1 ^∞ . The implementation of the algorithm in the computer algebra system Maple is described.     

Extended macro grammars and stack controlled machines

K-extended basic macro grammars are introduced, where K is any class of languages. The class B(K) of languages generated by such grammars is investigated, together with the class LB(K) of languages generated by the corresponding linear basic grammars. For any full semi-AFL K, B(K) is a full AFL closed under iterated LB(K)-substitution, but not necessarily under substitution. For any machine type D, the stack controlled machine type corresponding to D is introduced, denoted S(D), and the checking-stack controlled machine type CS(D). The data structure of this machine is a stack which controls a pushdown of data structures from D. If D accepts K, then S(D) accepts B(K) and CS(D) accepts LB(K). Thus the classes B(K) are characterized by stack controlled machines and the classes LB(K), i.e., the full hyper-AFLs, by checking-stack controlled machines. A full basic-AFL is a full AFL K such that B(K) ? K. Every full basic-AFL is a full hyper-AFL, but not vice versa. The class of OI macro languages (i.e., indexed languages, i.e., nested stack automaton languages) is a full basic-AFL, properly containing the smallest full basic-AFL. The latter is generated by the ultrabasic macro grammars and accepted by the nested stack automata with bounded depth of nesting (and properly contains the stack languages, the ETOL languages, i.e., the smallest full hyper-AFL, and the basic macro languages). The full basic-AFLs are characterized by bounded nested stack controlled machines.     

Mapping two complete binary trees into the star graph with quick fault recovery

This paper proposes an approach for embedding two complete binary trees (CBT) into ann-dimensional star graph (S _n), and provides a fault-tolerant scheme for the trees. First, aCBT with height Σ _m=2 ⁿ ?logm? is embedded into theS _n with dilation 3. The height of theCBT is very close to ?Σ _m=2 ⁿ logm?, the height of the largest possibleCBT which can be embedded into theS _n. Shifting the firstCBT by generating function productg ₂ g ₃ g ₄ g ₃, anotherCBT with height Σ _m=2 ⁿ ?logm? can also be embedded into theS _n without conflicting with the first one. Moreover, if three-eights of nodes in the firstCBT and all nodes in the secondCBT are faulty, all of them can be recovered. Under the condition that the firstCBT with smaller height (?Σ _m=2 ⁿ logm? ? 1) is embedded, all the replacement nodes will be free. As a consequence, even in the case that all nodes in the two trees are faulty, they can be recovered in the smallest number of recovery steps and only with dilation 5.     

On the hilbert transform of bounded bandlimited signals

In this paper we analyze the Hilbert transform and existence of the analytical signal for the space B _?? ^?? of bandlimited signals that are bounded on the real axis. Originally, the theory was developed for signals in L ²(?) and then extended to larger signal spaces. While it is well known that the common integral representation of the Hilbert transform may diverge for some signals in B _?? ^?? and that the Hilbert transform is not a bounded operator on B _?? ^?? , it is nevertheless possible to define the Hilbert transform for the space B _?? ^?? . We use a definition that is based on the H ¹-BMO(?) duality. This abstract definition, which can be used for general bounded signals, gives no constructive procedure to compute the Hilbert transform. However, for the practically important special case of bounded bandlimited signals, we can provide such an explicit procedure by giving a closed-form expression for the Hilbert transform. Further, it is shown that the Hilbert transform of a signal in B _?? ^?? is still bandlimited but not necessarily bounded. With these results we continue the work of [1, 2].     

On the complexity of algorithms for the translation of polynomials

Three algorithms for computing the coefficients of translated polynomials are discussed and compared from the point of view of complexity. The two classical translation algorithms based on explicit application of the Taylor expansion theorem and the Ruffini-Horner method, respectively, have complexityO (n ²). A third algorithm based on the fast Fourier transform is shown to have complexityO (n logn). However, when the cost of arithmetic operations is explicitly taken into consideration, the Ruffini-Horner algorithm is one order of magnitude better than the one based on the Taylor expansion and competes quite well with the algorithm based on the fast Fourier transform.     

A model classifying algorithms as inherently sequential with applications to graph searching

A model is proposed that can be used to classify algorithms as inherently sequential. The model captures the internal computations of algorithms. Previous work in complexity theory has focused on the solutions algorithms compute. Direct comparison of algorithms within the framework of the model is possible. The model is useful for identifying hard to parallelize constructs that should be avoided by parallel programmers. The model's utility is demonstrated via applications to graph searching. A stack breadth-first search (BFS) algorithm is analyzed and proved inherently sequential. The proof technique used in the reduction is a new one. The result for stack BFS sharply contrasts with a result showing that a queue based BFS algorithm is in NC. An NC algorithm to compute greedy depth-first search numbers in a dag is presented, and a result proving that a combination search strategy called breadth-depth search is inherently sequential is also given.     

Interpolation that leads to the narrowest intervals and its application to expert systems and intelligent control

In many real-life situations, we want to reconstruct the dependencyy=f(x ₁,…, x_n) from the known experimental resultsx _i ^(k) , y^(k). In other words, we want tointerpolate the functionf from its known valuesy ^(k)=f(x ₁ ^(k) ,…, x _n ^(k) ) in finitely many points $\bar x^{(k)} = (x_1^{(k)} , \ldots ,x_n^{(k)} )$ , 1≤k≤N There are many functions that go through given points. How to choose one of them? The main goal of findingf is to be able to predicty based onx _i. If we getx _i from measurements, then usually, we only getintervals that containx _i. As a result of applyingf, we get an interval y of possible values ofy. It is reasonable to choosef for which the resulting interval is the narrowest possible. In this paper, we formulate this choice problem in mathematical terms, solve the corresponding problem for several simple cases, and describe the application of these solutions to intelligent control.     

Numerical solution for the one-phase Stefan problem by Piecewise constant approximation of the interface

The classical one-phase one-dimensional Stefan problem is numerically solved on rectangles,R _j , of increasing size controlled by the Stefan condition. This approach is based on a scheme introduced by E. Di Benedetto and R. Spigler in 1983. The practical implementation rests on the representation viathermal potentials of the solutionu ^j (x, t) to the heat equation inR _j . The quantityu _x ^j (x _j ,jΔt) which determines the (j+1)-th rectangle is evaluatedanalytically by solving explicitly an integral equation. The solution inR _j+1 is then obtained bynumerically evaluating a further integral expression. The algorithm is tested by solving two problems whose solution is explicitly known. Convergence, stability and convergence rate as Δx→0, Δt→0 have been tested and plots are shown.     

Fine structure of a one-dimensional discrete point system

We consider a system of N points x ₁ < ... < x _N on a segment of the real line. An ideal system (crystal) is a system where all distances between neighbors are the same. Deviation from idealness is characterized by a system of finite differences ? _i ¹ = x _x+1 ? x _i , ? _i ^k+1 = ? _i+1 ^k ? ? _i ^k , for all possible i and k. We find asymptotic estimates as N ?? ??, k????, for a system of points minimizing the potential energy of a Coulomb system in an external field.     

LDPC比特翻转译码算法的分析与改进

利用统计译码思想由LDPC（Low Density Parity Check）码校验矩阵通过矢量的线性组合构造出一个新的低密度校验矢量集合，并结合LDPC码并行比特翻转译码算法的环检测等特点的分析，提出了一种新的硬判决译码方案。仿真结果表明：改进算法在译码性能上接近BP算法，又保持了并行比特翻转算法迭代次数少的优点。