Critical Configurations for 1-View in Projections from ℙ<Superscript>k</Superscript> → ℙ<Superscript>2</Superscript>

In this paper we describe, from a theoretical point of view, critical configurations for the projective reconstruction of a set of points, for a single view, i.e. for calibration of a camera, in the case of projections from ℙ^k to ℙ² for k ≥ 4. We give first a general result describing these critical loci in ℙ^k, which, if irreducible, are algebraic varieties of dimension k−2 and degree 3. If k=4 they can be either a smooth ruled surface or a cone and if k = 5 they can be a smooth three dimensional variety, ruled in planes, or a cone. If k≥ 6, the variety is always a cone, the vertex of which has dimension at least k − 6. The reducible cases are studied in Appendix A. These results are then applied to determine explicitly the critical loci for the projections from ℙ^k which arise from the dynamic scenes in ℙ³ considered in [13]. Marina Bertolini is currently Associate Professor of Geometry at the Department of Mathematics at the Università degli Studi di Milano, Italy. Her main field of research is Complex Projective Algebraic Geometry, with particular interest for the classification of projective varieties and for the geometry of Grassmann varieties. On these topics M. Bertolini has published more than twenty reviewed papers on national and international journals. She has been for some years now interested also in applications of Algebraic Geometry to Computer Vision problems. Cristina Turrini is Associate Professor of Geometry at the Department of Mathematics of Università degli Studi di Milano, Italy. Her main research interest is Complex Projective Algebraic Geometry: subvarieties of Grassmannians, special varieties, automorphisms, classification. In the last two years she has started to work on applications of Algebraic Geometry to problems of Computer Vision. She is author or co-author of about thirty reviewed papers. She is also involved in popularization of Mathematics, and on this subject she is co-editor of some books.     

Augmenting the Rigidity of a Graph in <Emphasis Type="Italic">R</Emphasis><Superscript>2</Superscript>

Given a Laman graph G, i.e. a minimally rigid graph in R ², we provide a Θ(n ²) algorithm to augment G to a redundantly rigid graph, by adding a minimum number of edges. Moreover, we prove that this problem of augmenting is NP-hard for an arbitrary rigid graph G in R ².     

Solving Connected Dominating Set Faster than 2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

In the connected dominating set problem we are given an n-node undirected graph, and we are asked to find a minimum cardinality connected subset S of nodes such that each node not in S is adjacent to some node in S. This problem is also equivalent to finding a spanning tree with maximum number of leaves. Despite its relevance in applications, the best known exact algorithm for the problem is the trivial Ω(2 ⁿ ) algorithm that enumerates all the subsets of nodes. This is not the case for the general (unconnected) version of the problem, for which much faster algorithms are available. Such a difference is not surprising, since connectivity is a global property, and non-local problems are typically much harder to solve exactly. In this paper we break the 2 ⁿ barrier, by presenting a simple O(1.9407 ⁿ ) algorithm for the connected dominating set problem. The algorithm makes use of new domination rules, and its analysis is based on the Measure and Conquer technique. An extended abstract of this paper appeared in the proceedings of FSTTCS’06. Fedor V. Fomin was additionally supported by the Research Council of Norway.     

Tree Structure for Contractible Regions in ℝ<Superscript>3</Superscript>

For contractible regions ωin ℝ³ with generic smooth boundary, we determine the global structure of the Blum medial axis M. We give an algorithm for decomposing M into “irreducible components” which are attached to each other along “fin curves”. The attaching cannot be described by a tree structure as in the 2D case. However, a simplified but topologically equivalent medial structure ̂ M with the same irreducible components can be described by a two level tree structure. The top level describes the simplified form of the attaching, and the second level tree structure for each irreducible component specifies how to construct the component by attaching smooth medial sheets to the network of Y-branch curves. The conditions for these structures are complete in the sense that any region whose Blum medial axis satisfies the conditions is contractible.     

A Hierarchical Extension of the <Emphasis Type="Italic">D</Emphasis><Superscript>*</Superscript> Algorithm

In this paper a contribution to the practice of path planning using a new hierarchical extension of the D^* algorithm is introduced. A hierarchical graph is stratified into several abstraction levels and used to model environments for path planning. The hierarchical D^* algorithm uses a down-top strategy and a set of pre-calculated trajectories in order to improve performance. This allows optimality and specially lower computational time. It is experimentally proved how hierarchical search algorithms and on-line path planning algorithms based on topological abstractions can be combined successfully.     

Robust polynomial classifier using <Emphasis Type="Italic">L</Emphasis><Superscript>1</Superscript>-<Emphasis Type="Italic">norm</Emphasis> minimization

In this paper we present a robust polynomial classifier based on L ¹-norm minimization. We do so by reformulating the classifier training process as a linear programming problem. Due to the inherent insensitivity of the L ¹-norm to influential observations, class models obtained via L ¹-norm minimization are much more robust than their counterparts obtained by the classical least squares minimization (L ²-norm). For validation purposes, we apply this method to two recognition problems: character recognition and sign language recognition. Both are examined under different signal to noise ratio (SNR) values of the test data. Results show that L ¹-norm minimization provides superior recognition rates over L ²-norm minimization when the training data contains influential observations especially if the test dataset is noisy.     

Multiphase Soft Segmentation with Total Variation and <Emphasis Type="Italic">H</Emphasis><Superscript>1</Superscript> Regularization

In this paper, we propose a variational soft segmentation framework inspired by the level set formulation of multiphase Chan-Vese model. We use soft membership functions valued in [0,1] to replace the Heaviside functions of level sets (or characteristic functions) such that we get a representation of regions by soft membership functions which automatically satisfies the sum to one constraint. We give general formulas for arbitrary N-phase segmentation, in contrast to Chan-Vese’s level set method only 2 ^m -phase are studied. To ensure smoothness on membership functions, both total variation (TV) regularization and H ¹ regularization used as two choices for the definition of regularization term. TV regularization has geometric meaning which requires that the segmentation curve length as short as possible, while H ¹ regularization has no explicit geometric meaning but is easier to implement with less parameters and has higher tolerance to noise. Fast numerical schemes are designed for both of the regularization methods. By changing the distance function, the proposed segmentation framework can be easily extended to the segmentation of other types of images. Numerical results on cartoon images, piecewise smooth images and texture images demonstrate that our methods are effective in multiphase image segmentation.     

Low-density incomplete <Emphasis Type="Italic">LDL</Emphasis><Superscript><Emphasis Type="Italic">T</Emphasis></Superscript> factorizations

A particular class of incomplete factorizations is proposed as preconditioners for the linear system Ax = b where A is a symmetric, large and sparse matrix. The ILDL ^T< (p) factorization (p = 1,2,3, …) determines the density of the lower triangular matrix L selecting the p largest off-diagonal entries of each column during the Gaussian elimination process. This selection may be computationally expensive, but the effectiveness of the preconditioner allows us to choose very low-density factors to reduce both work time and storage requirements. This incomplete factorization can be performed reliably on H-matrices. When A is a positive definite matrix, but not an H-matrix, one can perform an incomplete factorization if positive off-diagonal entries are removed or reduced and diagonally compensated. Numerical results for a variety of problems and comparisons with other incomplete factorizations are presented. Received: August 2002 / Accepted: December 2002 RID="*" ID="*"This work was supported by the Spanish grant BFM 2001-2641.     

On the application of the <Emphasis Type="Italic">P</Emphasis><Subscript>1</Subscript><Superscript><Emphasis Type="Italic">mod</Emphasis></Superscript> element to incompressible flow problems

We consider the application of the nonconforming P₁^mod element to the approximation of the velocity in the incompressible Stokes and Navier–Stokes equations. We prove the uniform validity of an inf–sup condition if the pressure is approximated by piecewise constant functions. Under additional assumptions, we also prove the inf–sup condition for discontinuous piecewise linear approximations of the pressure. Numerical results show that the P₁^mod element allows to obtain significantly better approximations of the velocity than the Crouzeix–Raviart element.     

<Emphasis Type="Italic">H</Emphasis><Superscript>1</Superscript>-interpolation on quadrilateral and hexahedral meshes with hanging nodes

We propose a Scott-Zhang type finite element interpolation operator of first order for the approximation of H ¹-functions by means of continuous piecewise mapped bilinear or trilinear polynomials. The novelty of the proposed interpolation operator is that it is defined for general non-affine equivalent quadrilateral and hexahedral elements and so-called 1-irregular meshes with hanging nodes. We prove optimal local approximation properties of this interpolation operator for functions in H ¹. As necessary ingredients we provide a definition of a hanging node and a rigorous analysis of the issue of constrained approximation which cover both the two- and three-dimensional case in a unified fashion.      

Exact 3-satisfiability is decidable in time <Emphasis Type="Italic">O</Emphasis>(2<Superscript>0.16254<Emphasis Type="Italic">n</Emphasis></Superscript>)

Let F=C ₁C _m be a Boolean formula in conjunctive normal form over a set V of n propositional variables, s.t. each clause C _i contains at most three literals l over V. Solving the problem exact 3-satisfiability (X3SAT) for F means to decide whether there is a truth assignment setting exactly one literal in each clause of F to true (1). As is well known X3SAT is NP-complete [6]. By exploiting a perfect matching reduction we prove that X3SAT is deterministically decidable in time O(2^0.18674n ). Thereby we improve a result in [2,3] stating X3SATO(2^0.2072n ) and a bound of O(2^0.200002n ) for the corresponding enumeration problem #X3SAT stated in a preprint [1]. After that by a more involved deterministic case analysis we are able to show that X3SATO(2^0.16254n ).     

A Multi-Scale Vectorial L<Superscript><Emphasis Type="Italic">τ</Emphasis></Superscript>-TV Framework for Color Image Restoration

A general multi-scale vectorial total variation model with spatially adapted regularization parameter for color image restoration is introduced in this paper. This total variation model contains an L ^τ -data fidelity for any τ∈[1,2]. The use of a spatial dependent regularization parameter improves the reconstruction of features in the image as well as an adequate smoothing for the homogeneous parts. The automated adaptation of this regularization parameter is made according to local statistical characteristics of the noise which contaminates the image. The corresponding multiscale vectorial total variation model is solved by Fenchel-duality and inexact semismooth Newton techniques. Numerical results are presented for the cases τ=1 and τ=2 which reconstruct images contaminated with salt-and-pepper noise and Gaussian noise, respectively.     

Equivalence of <Emphasis Type="Italic">ε</Emphasis> -Approximate Separation and Optimization in Fixed Dimensions<Superscript><Emphasis Type="Italic">1</Emphasis></Superscript>

Given a closed, convex set X\subseteq \bbR ⁿ , containing the origin, we consider the problem (P) : max {c^\T x\colon x ∈ X} . We show that, for a fixed dimension, n , and fixed \eps , 0 <\eps<1 , the existence of a combinatorial, strongly polynomial \eps -approximation separation algorithm for the set X is equivalent to the existence of a combinatorial, strongly polynomial \eps -approximation optimization algorithm for the problem (P) . Received June 5, 1996; revised September 25, 1997.     

Prefetching J<Superscript>+</Superscript>-Tree: A Cache-Optimized Main Memory Database Index Structure

As the speed gap between main memory and modern processors continues to widen, the cache behavior becomes more important for main memory database systems (MMDBs). Indexing technique is a key component of MMDBs. Unfortunately, the predominant indexes — B⁺-trees and T-trees — have been shown to utilize cache poorly, which triggers the development of many cache-conscious indexes, such as CSB⁺-trees and pB⁺-trees. Most of these cache-conscious indexes are variants of conventional B⁺-trees, and have better cache performance than B⁺-trees. In this paper, we develop a novel J ⁺ -tree index, inspired by the Judy structure which is an associative array data structure, and propose a more cache-optimized index — Prefetching J ⁺ -tree (pJ⁺-tree), which applies prefetching to J⁺-tree to accelerate range scan operations. The J⁺-tree stores all the keys in its leaf nodes and keeps the reference values of leaf nodes in a Judy structure, which makes J⁺-tree not only hold the advantages of Judy (such as fast single value search) but also outperform it in other aspects. For example, J⁺-trees can achieve better performance on range queries than Judy. The pJ⁺-tree index exploits prefetching techniques to further improve the cache behavior of J⁺-trees and yields a speedup of 2.0 on range scans. Compared with B⁺-trees, CSB⁺-trees, pB⁺-trees and T-trees, our extensive experimental study shows that pJ⁺-trees can provide better performance on both time (search, scan, update) and space aspects.     

The Number of Tree Stars Is <Emphasis Type="Italic">O</Emphasis><Superscript>*</Superscript>(1.357<Superscript><Emphasis Type="Italic">k</Emphasis></Superscript>)

Every rectilinear Steiner tree problem admits an optimal tree T ^* which is composed of tree stars. Moreover, the currently fastest algorithms for the rectilinear Steiner tree problem proceed by composing an optimum tree T ^* from tree star components in the cheapest way. The efficiency of such algorithms depends heavily on the number of tree stars (candidate components). Fößmeier and Kaufmann (Algorithmica 26, 68–99, 2000) showed that any problem instance with k terminals has a number of tree stars in between 1.32 ^k and 1.38 ^k (modulo polynomial factors) in the worst case. We determine the exact bound O ^*(ρ ^k ) where ρ≈1.357 and mention some consequences of this result.     

The <Emphasis Type="Italic">L</Emphasis><Superscript>2</Superscript>-Optimality of the IIPG Method for Odd Degrees of Polynomial Approximation in 1D

The paper deals with a numerical analysis of the incomplete interior penalty Galerkin (IIPG) method applied to one dimensional Poisson problem. Based on a particular choice of the interior penalty parameter σ (order of O(h ⁻¹)), we derive the optimal error estimate in the L ²-norm for odd degrees of polynomial approximation for locally quasi-uniform meshes. Moreover, we show that only the mentioned choice of the penalty parameter leads to optimal orders of convergence. Finally, presented numerical experiments verify the theoretical results.     

Abstract Data Types Can Have Inequations<Superscript>1</Superscript>

Abstract. This work proposes a typed functional wide-spectrum language, Funiq, for both programming and specification as an extension of Cardelli-Wegners Fun enriched with the fixed-point construction on expressions and inequational refinements (as assertions) for types. The type system of our wide-spectrum Funiq language is shown to be a conservative extension of that of the original Fun and sound with respect to the complete PER semantics for types.¹ An extended abstract of an earlier version of this work appeared under the title basic properties of data types with inequational refinements (extended abstract) without any proofs and using a slightly (but non-trivially, from the technical viewpoint) different formulation of the system in Typed Lambda Calculi and Applications (ed. by M. Dezani-Ciancaglini and G. Plotkin), Lecture Notes in Computer Science 902, 279–296 (Springer-Verlag); Proceedings of the 2nd International Conference on Typed Lambda Calculi and Applications, TLCA95, held in Edinburgh, UK, 10–12 April 1995.     

GS<Superscript>3</Superscript>: a Grid Storage System with Security Features

Technological trend and the advent of worldwide networks, such as the Internet, made computing systems more and more powerful, increasing both processing and storage capabilities. In Grid computing infrastructures, the data storage subsystem is physically distributed among several nodes and logically shared among several users. This highlights the necessity of a) availability for authorized users only, b) confidentiality, and c) integrity of information and data: in one term security. In this work we face the problem of data security in Grid, by proposing a lightweight cryptography algorithm combining the strong and highly secure asymmetric cryptography technique (RSA) with the symmetric cryptography (AES). The proposed algorithm, we named Grid secure storage system (GS³), has been implemented on top of the Grid file access library (GFAL) of the gLite middleware, in order to provide a file system service with cryptography capability and POSIX interface. The choice of implementing GS³ as a file system, the GS3FS, allows to protect the file system structure also, and to overcome the well-known problem of file rewriting in gLite/GFAL environments. In the specification of the GS3FS, particular care is addressed on providing a usable user interface and on implementing a file system that has low impact on the middleware. The final result is the introduction of a new storage Grid service into the gLite middleware, whose overall characteristics are never offered before, at the best of authors’ knowledge. The paper describes and details both the GS³ algorithm and its implementation; the performance of such implementation are evaluated discussing the obtained results and possible application scenarios in order to demonstrate its effectiveness and usefulness.     

Finding a Minimum-depth Embedding of a Planar Graph in <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>4</Superscript>) Time

Consider an n-vertex planar graph G. The depth of an embedding Γ of G is the maximum distance of its internal faces from the external one. Several researchers pointed out that the quality of a planar embedding can be measured in terms of its depth. We present an O(n ⁴)-time algorithm for computing an embedding of G with minimum depth. This bound improves on the best previous bound by an O(nlog n) factor. As a side effect, our algorithm improves the bounds of several algorithms that require the computation of a minimum-depth embedding.     

A new matrix approach to real FFTs and convolutions of length 2<Superscript><Emphasis Type="Italic">k</Emphasis></Superscript>

A new matrix, scaled odd tail, SOT, is introduced. This new matrix is used to derive real and complex FFT algorithms for lengths n = 2 ^k . A compromise is reached between Fourier transform and polynomial transform methods for computing the action of cyclic convolutions. Both of these methods lead to arithmetic operation counts that are better than previously published results. A minor improvement is also demonstrated that enables us to compute the actions of Fermat prime order FFTs in fewer additions than previously available algorithms.