Unique Covering Problems with Geometric Sets

The Exact Cover problem takes a universe U of n elements, a family F of m subsets of U and a positive integer k, and decides whether there exists a subfamily(set cover) F' of size at most k such that each element is covered by exactly one set. The Unique Cover problem also takes the same input and decides whether there is a subfamily F' subset of F such that at least k of the elements F' covers are covered uniquely(by exactly one set). Both these problems are known to be NP-complete. In the parameterized setting, when parameterized by k, Exact Cover is W1]-hard. While Unique Cover is FPT under the same parameter, it is known to not admit a polynomial kernel under standard complexity-theoretic assumptions. In this paper, we investigate these two problems under the assumption that every set satisfies a given geometric property Pi. Specifically, we consider the universe to be a set of n points in a real space R-d, d being a positive integer. When d = 2 we consider the problem when. requires all sets to be unit squares or lines. When d > 2, we consider the problem where. requires all sets to be hyperplanes in R-d. These special versions of the problems are also known to be NP-complete. When parameterizing by k, the Unique Cover problem has a polynomial size kernel for all the above geometric versions. The Exact Cover problem turns out to be W1]-hard for squares, but FPT for lines and hyperplanes. Further, we also consider the Unique Set Cover problem, which takes the same input and decides whether there is a set cover which covers at least k elements uniquely. To the best of our knowledge, this is a new problem, and we show that it is NP-complete (even for the case of lines). In fact, the problem turns out to be W1]-hard in the abstract setting, when parameterized by k. However, when we restrict ourselves to the lines and hyperplanes versions, we obtain FPT algorithms.

Lower Bounds for Sums of Powers of Low Degree Univariates

We consider the problem of representing a univariate polynomial f(x) as a sum of powers of low degree polynomials. We prove a lower bound of Omega(root d/t) for writing an explicit univariate degree-d polynomial f(x) as a sum of powers of degree-t polynomials.

CCD: Connected Component Descriptor for Robust Mosaicing of Camera-Captured Document Images

We propose a robust method for mosaicing of document images using features derived from connected components. Each connected component is described using the Angular Radial Tran. form (ART). To ensure geometric consistency during feature matching, the ART coefficients of a connected component are augmented with those of its two nearest neighbors. The proposed method addresses two critical issues often encountered in correspondence matching: (i) The stability of features and (ii) Robustness against false matches due to the multiple instances of characters in a document image. The use of connected components guarantees a stable localization across images. The augmented features ensure a successful correspondence matching even in the presence of multiple similar regions within the page. We illustrate the effectiveness of the proposed method on camera captured document images exhibiting large variations in viewpoint, illumination and scale.

Functional correlation of bacterial LuxS with their quaternary associations: interface analysis of the structure networks

Background The genome of a wide variety of prokaryotes contains the luxS gene homologue, which encodes for the protein S-ribosylhomocysteinelyase (LuxS). This protein is responsible for the production of the quorum sensing molecule, AI-2 and has been implicated in a variety of functions such as flagellar motility, metabolic regulation, toxin production and even in pathogenicity. A high structural similarity is present in the LuxS structures determined from a few species. In this study, we have modelled the structures from several other species and have investigated their dimer interfaces. We have attempted to correlate the interface features of LuxS with the phenotypic nature of the organisms. Results The protein structure networks (PSN) are constructed and graph theoretical analysis is performed on the structures obtained from X-ray crystallography and on the modelled ones. The interfaces, which are known to contain the active site, are characterized from the PSNs of these homodimeric proteins. The key features presented by the protein interfaces are investigated for the classification of the proteins in relation to their function. From our analysis, structural interface motifs are identified for each class in our dataset, which showed distinctly different pattern at the interface of LuxS for the probiotics and some extremophiles. Our analysis also reveals potential sites of mutation and geometric patterns at the interface that was not evident from conventional sequence alignment studies. Conclusion The structure network approach employed in this study for the analysis of dimeric interfaces in LuxS has brought out certain structural details at the side-chain interaction level, which were elusive from the conventional structure comparison methods. The results from this study provide a better understanding of the relation between the luxS gene and its functional role in the prokaryotes. This study also makes it possible to explore the potential direction towards the design of inhibitors of LuxS and thus towards a wide range of antimicrobials.

Efficient Output-Sensitive Construction of Reeb Graphs

The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. This paper describes a near-optimal two-step algorithm that constructs the Reeb graph of a Morse function defined over manifolds in any dimension. The algorithm first identifies the critical points of the input manifold, and then connects these critical points in the second step to obtain the Reeb graph. A simplification mechanism based on topological persistence aids in the removal of noise and unimportant features. A radial layout scheme results in a feature-directed drawing of the Reeb graph. Experimental results demonstrate the efficiency of the Reeb graph construction in practice and its applications.

Instability of laminated composite thin-walled open-section beams

Instability of thin-walled open-section laminated composite beams is studied using the finite element method. A two-noded, 8 df per node thin-walled open-section laminated composite beam finite element has been used. The displacements of the element reference axis are expressed in terms of one-dimensional first order Hermite interpolation polynomials, and line member assumptions are invoked in formulation of the elastic stiffness matrix and geometric stiffness matrix. The nonlinear expressions for the strains occurring in thin-walled open-section beams, when subjected to axial, flexural and torsional loads, are incorporated in a general instability analysis. Several problems for which continuum solutions (exact/approximate) are possible have been solved in order to evaluate the performance of finite element. Next its applicability is demonstrated by predicting the buckling loads for the following problems of laminated composites: (i) two layer (45°/−45°) composite Z section cantilever beam and (ii) three layer (0°/45°/0°) composite Z section cantilever beam.

Studies of phosphazenes. Part 15. Chloro(phenoxy)cyclotetraphosphazenes, N4P4Cl8-n(OPh)n

The reaction of N4P4Cl8(1) with sodium phenoxide (or phenol in the presence of triethylamine) has been studied under a variety of experimental conditions. The chloro(phenoxy)-derivatives, N4P4Cl8-n(OPh)n[n= 1 or 2 (mixture of four non-geminal isomers), 3(mixture of non-geminal isomers), 4(mixture of isomers), 5(mixture of isomers), 6(mixture of four non-geminal isomers), or 8], have been isolated by column chromatography over silica gel. Attempts to separate geometric isomers were unsuccessful. Structural elucidation of the products is based on the 31P n.m.r. data for the chloro-precursors and 1H and 31P n.m.r. spectra of the dimethylamino- and/or methoxy-derivatives. The chlorine-replacement pattern is discussed.

Effect of a magnetic field on the flow and blood oxygenation in channels of variable cross-section

The effect of a magnetic field on the flow and oxygenation of an incompressible Newtonian conducting fluid in channels with irregular boundaries has been investigated. The geometric parameter δ, which is a ratio of the mean half width of the channel d to the characteristic length λ along the channel over which the significant changes in the flow quantities occur, has been used for perturbing the governing equations. Closed form solutions of the various order equations are presented for the stream function. The equations for oxygen partial pressure remain nonlinear even after perturbation, therefore a numerical solution is presented. The expressions for shear stress at a wall and pressure distributions are derived. Here the separation in the flow occurs at a higher Reynolds number than the corresponding non-magnetic case. It is found that the magnetic field has an effect on local oxygen concentration but has a little effect on the saturation length.

Efficient algorithms for computing Reeb graphs

The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. We describe an algorithm that constructs the Reeb graph of a Morse function defined on a 3-manifold. Our algorithm maintains connected components of the two dimensional levels sets as a dynamic graph and constructs the Reeb graph in O(nlogn+nlogg(loglogg)3) time, where n is the number of triangles in the tetrahedral mesh representing the 3-manifold and g is the maximum genus over all level sets of the function. We extend this algorithm to construct Reeb graphs of d-manifolds in O(nlogn(loglogn)3) time, where n is the number of triangles in the simplicial complex that represents the d-manifold. Our result is a significant improvement over the previously known O(n2) algorithm. Finally, we present experimental results of our implementation and demonstrate that our algorithm for 3-manifolds performs efficiently in practice.

Cation-induced crown porphyrin dimers of oxovanadium(IV)

Oxovanadium(1V) porphyrins appended with crown ether (benzo-15-crown-5) at the 5 (mono), the 5 and 10115 (cis/trans bis), the 5, 10, and 15 (tris), and the 5, 10, 15, and 20 (tetrakis) positions have been synthesized. The cation complexation behavior of these cavity-bearing porphyrins has been studied by using optical aborption and ESR spectral methods. The cations K+, Cs+, NH4+, and Ba2+, which require two crown ether cavities for complexation, induce dimerization of the porphyrins. The cation-induced dimerization constants for a representative tetrasubstituted porphyrin vary as K+ > Ba2+ > Cs+ - NH4+, and the relative stabilities of the dimers are dependent on the type of the substitution, tetrakis > tris > cis bis. ESR spectra recorded at a sample temperature of 77 K have low-field components attributed to Ah& = f 2 transitions, providing further evidence for the existence of dimers in solutions. The eclipsed sandwich dimers have V-V distances in the range 4.70 A. The relative distributions of oxovanadium crown porphyrins in terms of monomeric and dimeric forms rest on the geometric dispositions of the crown ether appendages.

Oxygen transfer in circular surface aeration tanks

Surface aeration systems employed in activated sludge plants are the most energy-intensive units of the plants and typically account for a higher percentage of the treatment facility's total energy use. The geometry of the aeration tank imparts a major effect on the system efficiency. It is said that at optimal geometric onditions, systems exhibits the maximum efficiency. Thus the quantification of the optimal geometric conditions in surface aeration tanks is needed. Optimal geometric conditions are also needed to scale up the laboratory result to the field installation. In the present work, experimental studies have been carried out on baffled and unbaffled circular surface aeration tanks to ascertain the optimal geometric conditions. It is found that no optimal geometric conditions exist for the liquid/water depth in circular surface aeration tanks; however, for design purposes, a standard value has been assumed. Based on the optimal geometric conditions, a scale-up equation has been developed for the baffled circular surface aeration tanks.

Solid-State Acyl Migration In Salicylamides - An X-Ray Study Of The Ortho-Propionyl And Normal-Propionyl Derivatives

In recent years there has been an upsurge of interest in the study of organic reactions in the solid state. It is now realised that the crystalline matrix provides an extra-ordinary spatial control on the initiation and progress of these reactions. Electronic and dipolar effects which are important in solution are replaced by structural and geometric effects in solids. These 'spatial' or 'topochemical' aspects are important in understanding the mechanistic details of the reaction. In our laboratory, the thermally induced acyl migration in salicylamides from 0- to N- position in the solid state has been under study (Scheme 1). The structures of the acetyl and benzoyl derivatives (Ia,IIa, Ib and IIb) have been reported.

A reconsideration of phase relations in the Ti-Al-Mo and Ti-Al systems

A microstructural and X-ray investigation of Ti-AI-Mo alloys Ti-31 Al-15 Mo, Ti-31 Al-13 Mo, Ti-31Al-9Mo and Ti-35Al-9Mo (containing the Ti3Al, TiAl and β phases) indicates that the existing phase diagram of the ternary system for this composition range published by Ge Dhzhi-Min and Pylaeva is in error above 1473 K. An analysis of phase relations reveals that the error has arisen from their use of the Ti-AI diagram due to Bumps, Kessler and Hansen as a basis for generating the ternary. It is shown that a phase diagram of the ternary, consistent with the experimental results, can be generated using a version of the Ti-AI system due to Margolin. Simple geometric arguments are used to build up a new semi-quantitative description of the Ti-AI-Mo system which can be used as a basis for a detailed investigation of phase equilibria in this system.

Non-linear dynamic analysis of rotors by finite element method

Non-linear natural vibration characteristics and the dynamic response of hingeless and fully articulated rotors of rectangular cross-section are studied by using the finite element method. In the formulation of response problems, the global variables are augmented with appropriate additional variables, facilitating direct determination of sub-harmonic response. Numerical results are given showing the effect of the geometric non-linearity on the first three natural frequencies. Response analysis of typical rotors indicates a possibility of substantial sub-harmonic response especially in the fully articulated rotors widely adopted in helicopters.

Synergistic Execution of Stream Programs on Multicores with Accelerators

The StreamIt programming model has been proposed to exploit parallelism in streaming applications oil general purpose multicore architectures. The StreamIt graphs describe task, data and pipeline parallelism which can be exploited on accelerators such as Graphics Processing Units (GPUs) or CellBE which support abundant parallelism in hardware. In this paper, we describe a novel method to orchestrate the execution of if StreamIt program oil a multicore platform equipped with an accelerator. The proposed approach identifies, using profiling, the relative benefits of executing a task oil the superscalar CPU cores and the accelerator. We formulate the problem of partitioning the work between the CPU cores and the GPU, taking into account the latencies for data transfers and the required buffer layout transformations associated with the partitioning, as all integrated Integer Linear Program (ILP) which can then be solved by an ILP solver. We also propose an efficient heuristic algorithm for the work-partitioning between the CPU and the GPU, which provides solutions which are within 9.05% of the optimal solution on an average across the benchmark Suite. The partitioned tasks are then software pipelined to execute oil the multiple CPU cores and the Streaming Multiprocessors (SMs) of the GPU. The software pipelining algorithm orchestrates the execution between CPU cores and the GPU by emitting the code for the CPU and the GPU, and the code for the required data transfers. Our experiments on a platform with 8 CPU cores and a GeForce 8800 GTS 512 GPU show a geometric mean speedup of 6.94X with it maximum of 51.96X over it single threaded CPU execution across the StreamIt benchmarks. This is a 18.9% improvement over it partitioning strategy that maps only the filters that cannot be executed oil the GPU - the filters with state that is persistent across firings - onto the CPU.