Approximation algorithm for maximum independent set in planar traingle-free graphs

The maximum independent set problem is NP-complete even when restricted to planar graphs, cubic planar graphs or triangle free graphs. The problem of finding an absolute approximation still remains NP-complete. Various polynomial time approximation algorithms, that guarantee a fixed worst case ratio between the independent set size obtained to the maximum independent set size, in planar graphs have been proposed. We present in this paper a simple and efficient, O(|V|) algorithm that guarantees a ratio 1/2, for planar triangle free graphs. The algorithm differs completely from other approaches, in that, it collects groups of independent vertices at a time. Certain bounds we obtain in this paper relate to some interesting questions in the theory of extremal graphs.

A modular planar robotic manipulandum with end-point torque control.

Robotic manipulanda are extensively used in investigation of the motor control of human arm movements. They permit the application of translational forces to the arm based on its state and can be used to probe issues ranging from mechanisms of neural control to biomechanics. However, most current designs are optimized for studying either motor learning or stiffness. Even fewer include end-point torque control which is important for the simulation of objects and the study of tool use. Here we describe a modular, general purpose, two-dimensional planar manipulandum (vBOT) primarily optimized for dynamic learning paradigms. It employs a carbon fibre arm arranged as a parallelogram which is driven by motors via timing pulleys. The design minimizes the intrinsic dynamics of the manipulandum without active compensation. A novel variant of the design (WristBOT) can apply torques at the handle using an add-on cable drive mechanism. In a second variant (StiffBOT) a more rigid arm can be substituted and zero backlash belts can be used, making the StiffBOT more suitable for the study of stiffness. The three variants can be used with custom built display rigs, mounting, and air tables. We investigated the performance of the vBOT and its variants in terms of effective end-point mass, viscosity and stiffness. Finally we present an object manipulation task using the WristBOT. This demonstrates that subjects can perceive the orientation of the principal axis of an object based on haptic feedback arising from its rotational dynamics.

Recognition of Planar Segments in Point Cloud Based on Wavelet Transform

© 2005-2012 IEEE.Within industrial automation systems, three-dimensional (3-D) vision provides very useful feedback information in autonomous operation of various manufacturing equipment (e.g., industrial robots, material handling devices, assembly systems, and machine tools). The hardware performance in contemporary 3-D scanning devices is suitable for online utilization. However, the bottleneck is the lack of real-time algorithms for recognition of geometric primitives (e.g., planes and natural quadrics) from a scanned point cloud. One of the most important and the most frequent geometric primitive in various engineering tasks is plane. In this paper, we propose a new fast one-pass algorithm for recognition (segmentation and fitting) of planar segments from a point cloud. To effectively segment planar regions, we exploit the orthonormality of certain wavelets to polynomial function, as well as their sensitivity to abrupt changes. After segmentation of planar regions, we estimate the parameters of corresponding planes using standard fitting procedures. For point cloud structuring, a z-buffer algorithm with mesh triangles representation in barycentric coordinates is employed. The proposed recognition method is tested and experimentally validated in several real-world case studies.

A new approach for the solution of the optimal set-point tracking problem for nonlinear systems

In this paper, a discrete time dynamic integrated system optimisation and parameter estimation algorithm is applied to the solution of the nonlinear tracking optimal control problem. A version of the algorithm with a linear-quadratic model-based problem is developed and implemented in software. The algorithm implemented is tested with simulation examples.

Reduced complexity set-point following in self-tuning control

An external input signal is incorporated into a self-tuning controller which, although it is based on a CARMA system model, employs a state-space framework for control law calculations. Steady-state set point following can then be accomplished even when only a recursive least squares parameter estimation scheme is used, despite the fact that the disturbance affecting the system may well be coloured.

C(k)-solvability near the characteristic set for a class of planar complex vector fields of infinite type

This paper deals with semi-global C(k)-solvability of complex vector fields of the form L = partial derivative/partial derivative t + x(r) (a(x) + ib(x))partial derivative/partial derivative x, r >= 1, defined on Omega(epsilon) = (-epsilon, epsilon) x S(1), epsilon > 0, where a and b are C(infinity) real-valued functions in (-epsilon, epsilon). It is shown that the interplay between the order of vanishing of the functions a and b at x = 0 influences the C(k)-solvability at Sigma = {0} x S(1). When r = 1, it is permitted that the functions a and b of L depend on the x and t variables, that is, L = partial derivative/partial derivative t + x(a(x, t) + ib(x, t))partial derivative/partial derivative x, where (x, t) is an element of Omega(epsilon).

Gevrey solvability near the characteristic set for a class of planar complex vector fields of infinite type

We study the Gevrey solvability of a class of complex vector fields, defined on Omega(epsilon) = (-epsilon, epsilon) x S(1), given by L = partial derivative/partial derivative t + (a(x) + ib(x))partial derivative/partial derivative x, b not equivalent to 0, near the characteristic set Sigma = {0} x S(1). We show that the interplay between the order of vanishing of the functions a and b at x = 0 plays a role in the Gevrey solvability. (C) 2008 Elsevier Inc. All rights reserved.

Three-point functions and su(1 vertical bar 1) spin chains

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Gaussian deconvolution: a useful method for a form-free modeling of scattering data from mono- and multilayered planar systems

A new method for analysis of scattering data from lamellar bilayer systems is presented. The method employs a form-free description of the cross-section structure of the bilayer and the fit is performed directly to the scattering data, introducing also a structure factor when required. The cross-section structure (electron density profile in the case of X-ray scattering) is described by a set of Gaussian functions and the technique is termed Gaussian deconvolution. The coefficients of the Gaussians are optimized using a constrained least-squares routine that induces smoothness of the electron density profile. The optimization is coupled with the point-of-inflection method for determining the optimal weight of the smoothness. With the new approach, it is possible to optimize simultaneously the form factor, structure factor and several other parameters in the model. The applicability of this method is demonstrated by using it in a study of a multilamellar system composed of lecithin bilayers, where the form factor and structure factor are obtained simultaneously, and the obtained results provided new insight into this very well known system.

Phylogenetic approach reveals that virus genotype largely determines HIV set-point viral load

HIV virulence, i.e. the time of progression to AIDS, varies greatly among patients. As for other rapidly evolving pathogens of humans, it is difficult to know if this variance is controlled by the genotype of the host or that of the virus because the transmission chain is usually unknown. We apply the phylogenetic comparative approach (PCA) to estimate the heritability of a trait from one infection to the next, which indicates the control of the virus genotype over this trait. The idea is to use viral RNA sequences obtained from patients infected by HIV-1 subtype B to build a phylogeny, which approximately reflects the transmission chain. Heritability is measured statistically as the propensity for patients close in the phylogeny to exhibit similar infection trait values. The approach reveals that up to half of the variance in set-point viral load, a trait associated with virulence, can be heritable. Our estimate is significant and robust to noise in the phylogeny. We also check for the consistency of our approach by showing that a trait related to drug resistance is almost entirely heritable. Finally, we show the importance of taking into account the transmission chain when estimating correlations between infection traits. The fact that HIV virulence is, at least partially, heritable from one infection to the next has clinical and epidemiological implications. The difference between earlier studies and ours comes from the quality of our dataset and from the power of the PCA, which can be applied to large datasets and accounts for within-host evolution. The PCA opens new perspectives for approaches linking clinical data and evolutionary biology because it can be extended to study other traits or other infectious diseases.

Membrane lipid perturbation modifies the set point of the temperature of heat shock response in yeast.

Addition of a saturated fatty acid (SFA) induced a strong increase in heat shock (HS) mRNA transcription when cells were heat-shocked at 37 degrees C, whereas treatment with an unsaturated fatty acid (UFA) reduced or eliminated the level of HS gene transcription at 37 degrees C. Transcription of the delta 9-desaturase gene (Ole1) of Histoplasma capsulatum, whose gene product is responsible for the synthesis of UFA, is up-regulated in a temperature-sensitive strain. We show that when the L8-14C mutant of Saccharomyces cerevisiae, which has a disrupted Ole1 gene, is complemented with its own Ole1 coding region under control of its own promoter or Ole1 promoters of H. capsulatum, the level of HS gene transcription depends on the activity of the promoters. Fluorescence anisotropy of mitochondrial membranes of completed strains corresponded to the different activity of the Ole1 promoter used. We propose that the SFA/UFA ratio and perturbation of membrane lipoprotein complexes are involved in the perception of rapid temperature changes and under HS conditions disturbance of the preexisting membrane physical state causes transduction of a signal that induces transcription of HS genes.

Discontinuity spacing analysis in rock masses using 3D point clouds

The complete characterization of rock masses implies the acquisition of information of both, the materials which compose the rock mass and the discontinuities which divide the outcrop. Recent advances in the use of remote sensing techniques – such as Light Detection and Ranging (LiDAR) – allow the accurate and dense acquisition of 3D information that can be used for the characterization of discontinuities. This work presents a novel methodology which allows the calculation of the normal spacing of persistent and non-persistent discontinuity sets using 3D point cloud datasets considering the three dimensional relationships between clusters. This approach requires that the 3D dataset has been previously classified. This implies that discontinuity sets are previously extracted, every single point is labeled with its corresponding discontinuity set and every exposed planar surface is analytically calculated. Then, for each discontinuity set the method calculates the normal spacing between an exposed plane and its nearest one considering 3D space relationship. This link between planes is obtained calculating for every point its nearest point member of the same discontinuity set, which provides its nearest plane. This allows calculating the normal spacing for every plane. Finally, the normal spacing is calculated as the mean value of all the normal spacings for each discontinuity set. The methodology is validated through three cases of study using synthetic data and 3D laser scanning datasets. The first case illustrates the fundamentals and the performance of the proposed methodology. The second and the third cases of study correspond to two rock slopes for which datasets were acquired using a 3D laser scanner. The second case study has shown that results obtained from the traditional and the proposed approaches are reasonably similar. Nevertheless, a discrepancy between both approaches has been found when the exposed planes members of a discontinuity set were hard to identify and when the planes pairing was difficult to establish during the fieldwork campaign. The third case study also has evidenced that when the number of identified exposed planes is high, the calculated normal spacing using the proposed approach is minor than those using the traditional approach.

Observations on the topography of the plain of Troy; and on the principal objects within, and around it described, or alluded to, in the Iliad : shewing that the system of M. de Chevalier [i.e. Lechevalier], so long upheld, is founded on a most erroneous topography : and also, that the two sources, denominated the warm, and the cold, spring, on which his system materially rests, do not present any contrast; but are exactly alike in point of temperature; that is cold : with a map, in which the topography set forth by M. de Chevalier, is contrasted with the several statements of three other travellers in the Troad : also, a sketch of the western part of the region of Mount Ida /

Includes index.