New and improved results for packing identical unitary radius circles within triangles, rectangles and strips

The focus of study in this paper is the class of packing problems. More specifically, it deals with the placement of a set of N circular items of unitary radius inside an object with the aim of minimizing its dimensions. Differently shaped containers are considered, namely circles, squares, rectangles, strips and triangles. By means of the resolution of non-linear equations systems through the Newton-Raphson method, the herein presented algorithm succeeds in improving the accuracy of previous results attained by continuous optimization approaches up to numerical machine precision. The computer implementation and the data sets are available at http://www.ime.usp.br/similar to egbirgin/packing/. (C) 2009 Elsevier Ltd, All rights reserved.

Packing triangles in low degree graphs and indifference graphs

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2 + epsilon, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68-72]. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs. (C) 2007 Elsevier B.V. All rights reserved.

Missing levels in acoustic resonators

It is shown that the deviations of the experimental statistics of six chaotic acoustic resonators from Wigner-Dyson random matrix theory predictions are explained by a recent model of random missing levels. In these resonatorsa made of aluminum plates a the larger deviations occur in the spectral rigidity (SRs) while the nearest-neighbor distributions (NNDs) are still close to the Wigner surmise. Good fits to the experimental NNDs and SRs are obtained by adjusting only one parameter, which is the fraction of remaining levels of the complete spectra. For two Sinai stadiums, one Sinai stadium without planar symmetry, two triangles, and a sixth of the three-leaf clover shapes, was found that 7%, 4%, 7%, and 2%, respectively, of eigenfrequencies were not detected.

Influence of angiotensinogen and angiotensin-converting enzyme polymorphisms on cardiac hypertrophy and improvement on maximal aerobic capacity caused by exercise training

Background The allele threonine (T) of the angiotensinogen has been associated with ventricular hypertrophy in hypertensive patients and soccer players. However, the long-term effect of physical exercise in healthy athletes carrying the T allele remains unknown. We investigated the influence of methionine M or T allele of the angiotensinogen and D or I allele of the angiotensin-converting enzyme on left-ventricular mass index (LVMI) and maximal aerobic capacity in young healthy individuals after long-term physical exercise training. Design Prospective clinical trial. Methods Eighty-three policemen aged between 20 and 35 years (mean +/- SD 26 +/- 4.5 years) were genotyped for the M235T gene angiotensinogen polymorphism (TT, n=25; MM/MT, n=58) and angiotensin-converting enzyme gene insertion/deletion (I/D) polymorphism (11, n=18; DD/DI, n=65). Left-ventricular morphology was evaluated by echocardiography and maximal aerobic capacity (VO(2peak)) by cardiopulmonary exercise test before and after 17 weeks of exercise training (50-80% VO(2peak)). Results Baseline VO(2peak) and LVMI were similar between TT and MM/MT groups, and II and DD/DI groups. Exercise training increased significantly and similarly VO(2peak) in homozygous TT and MM/MT individuals, and homozygous II and DD/DI individuals. In addition, exercise training increased significantly LVMI in TT and MM/MT individuals (76.5 +/- 3 vs. 86.7 +/- 4, P=0.00001 and 76.2 +/- 2 vs. 81.4 +/- 2, P=0.00001, respectively), and II and DD/DI individuals (777 +/- 4 vs. 81.5 +/- 4, P=0.0001 and 76 +/- 2 vs. 83.5 +/- 2, P=0.0001, respectively). However, LVMI I in TT individuals was significantly greater than in MM/MT individuals (P=0.04). LVMI was not different between 11 and DD/DI individuals. Conclusion Left-ventricular hypertrophy caused by exercise training is exacerbated in homozygous TT individuals with angiotensinogen polymorphism. Eur J Cardiovasc Prev Rehabil 16:487-492 (C) 2009 The European Society of Cardiology

A 2-D Delaunay refinement algorithm using an initial prerefinement from the boundary mesh

An improvement to the quality bidimensional Delaunay mesh generation algorithm, which combines the mesh refinement algorithms strategy of Ruppert and Shewchuk is proposed in this research. The developed technique uses diametral lenses criterion, introduced by L. P. Chew, with the purpose of eliminating the extremely obtuse triangles in the boundary mesh. This method splits the boundary segment and obtains an initial prerefinement, and thus reducing the number of necessary iterations to generate a high quality sequential triangulation. Moreover, it decreases the intensity of the communication and synchronization between subdomains in parallel mesh refinement.

SAGE transcript profiling of the juvenile cambial region of Eucalyptus grandis

Despite the importance of Eucalyptus spp. in the pulp and paper industry, functional genomic approaches have only recently been applied to understand wood formation in this genus. We attempted to establish a global view of gene expression in the juvenile cambial region of Eucalyptus grandis Hill ex Maiden. The expression profile was obtained from serial analysis of gene expression (SAGE) library data produced from 3- and 6-year-old trees. Fourteen-base expressed sequence tags (ESTs) were searched against public Eucalyptus ESTs and annotated with GenBank. Altogether 43,304 tags were generated producing 3066 unigenes with three or more copies each, 445 with a putative identity, 215 with unknown function and 2406 without an EST match. The expression profile of the juvenile cambial region revealed the presence of highly frequent transcripts related to general metabolism and energy metabolism, cellular processes, transport, structural components and information pathways. We made a quantitative analysis of a large number of genes involved in the biosynthesis of cellulose, pectin, hemicellulose and lignin. Our findings provide insight into the expression of functionally related genes involved in juvenile wood formation in young fast-growing E. grandis trees.

Template-based quadrilateral mesh generation from imaging data

This paper describes a novel template-based meshing approach for generating good quality quadrilateral meshes from 2D digital images. This approach builds upon an existing image-based mesh generation technique called Imeshp, which enables us to create a segmented triangle mesh from an image without the need for an image segmentation step. Our approach generates a quadrilateral mesh using an indirect scheme, which converts the segmented triangle mesh created by the initial steps of the Imesh technique into a quadrilateral one. The triangle-to-quadrilateral conversion makes use of template meshes of triangles. To ensure good element quality, the conversion step is followed by a smoothing step, which is based on a new optimization-based procedure. We show several examples of meshes generated by our approach, and present a thorough experimental evaluation of the quality of the meshes given as examples.

Twofold adaptive partition of unity implicits

Partition of Unity Implicits (PUI) has been recently introduced for surface reconstruction from point clouds. In this work, we propose a PUI method that employs a set of well-observed solutions in order to produce geometrically pleasant results without requiring time consuming or mathematically overloaded computations. One feature of our technique is the use of multivariate orthogonal polynomials in the least-squares approximation, which allows the recursive refinement of the local fittings in terms of the degree of the polynomial. However, since the use of high-order approximations based only on the number of available points is not reliable, we introduce the concept of coverage domain. In addition, the method relies on the use of an algebraically defined triangulation to handle two important tasks in PUI: the spatial decomposition and an adaptive polygonization. As the spatial subdivision is based on tetrahedra, the generated mesh may present poorly-shaped triangles that are improved in this work by means a specific vertex displacement technique. Furthermore, we also address sharp features and raw data treatment. A further contribution is based on the PUI locality property that leads to an intuitive scheme for improving or repairing the surface by means of editing local functions.

Approximation algorithms and hardness results for the clique packing problem

For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F = {K(2)}. In this paper we provide new approximation algorithms and hardness results for the K(r)-packing problem where K(r) = {K(2), K(3,) . . . , K(r)}. We show that already for r = 3 the K(r)-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed r. For r = 3, 4, 5 we obtain better approximations. For r = 3 we obtain a simple 3/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldorsson. For r = 4, we obtain a (3/2 + epsilon)-approximation, and for r = 5 we obtain a (25/14 + epsilon)-approximation. (C) 2008 Elsevier B.V. All rights reserved.

Generating segmented meshes from textured color images

This paper presents a new framework for generating triangular meshes from textured color images. The proposed framework combines a texture classification technique, called W-operator, with Imesh, a method originally conceived to generate simplicial meshes from gray scale images. An extension of W-operators to handle textured color images is proposed, which employs a combination of RGB and HSV channels and Sequential Floating Forward Search guided by mean conditional entropy criterion to extract features from the training data. The W-operator is built into the local error estimation used by Imesh to choose the mesh vertices. Furthermore, the W-operator also enables to assign a label to the triangles during the mesh construction, thus allowing to obtain a segmented mesh at the end of the process. The presented results show that the combination of W-operators with Imesh gives rise to a texture classification-based triangle mesh generation framework that outperforms pixel based methods. Crown Copyright (C) 2009 Published by Elsevier Inc. All rights reserved.