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.

Cladistic analysis of the suborder Conulariina Miller and Gurley, 1896 (Cnidaria, Scyphozoa; Vendian-Triassic)

Results of a cladistic analysis of the suborder Conulariina Miller and Gurley, 1896, a major extinct (Vendian-Triassic) group of scyphozoan cnidarians, are presented. The analysis sought to test whether the three conulariid subfamilies (Conulariinae Walcott, 1886, Paraconulariinae Sinclair, 1952 and Ctenoconulariinae Sinclair, 1952) recognized in the Treatise on Invertebrate Paleontology ( TIP) are monophyletic. A total of 17 morphological characters were scored for 16 ingroup taxa, namely the genera Archaeoconularia, Baccaconularia, Climacoconus, Conularia, Conulariella, Conularina, Ctenoconularia, Eoconularia, Glyptoconularia, Metaconularia, Notoconularia, Paraconularia, Pseudoconularia, Reticulaconularia, Teresconularia and Vendoconularia. The extant medusozoan taxa Cubozoa, Stauromedusae, Coronatae and Semaeostomeae served as outgroups. Unweighted analysisof the data matrix yielded 1057 trees, and successive weighting analysis resulted in one of the 1057 original trees. The ingroup is monophyletic with two autapomorphies: (1) the quadrate geometry of the oral region; and (2) the presence of a mineralized (phosphatic) periderm. Within the ingroup, the clade (Vendoconularia, Teresconularia, Conularina, Eoconularia) is supported by the sinusoidal longitudinal geometry of the transverse ridges, and the much larger clade (Baccaconularia, Glyptoconularia, Metaconularia, Pseudoconularia, Conularia, Ctenoconularia, Archaeoconularia, Notoconularia, Climacoconus, Paraconularia, Reticulaconularia) is supported by the presence of external tubercles, which, however, were lost in the clade (Notoconularia, Climacoconus, Paraconularia, Reticulaconularia). As proposed by Van Iten et al. (2000), the clade (Notoconularia, Climacoconus, Paraconularia, Reticulaconularia) is supported by the termination and alternation of the transverse ribs in the corner sulcus. The previously recognized subfamilies Conulariinae, Paraconulariinae and Ctenoconulariinae were not recovered from this analysis. The diagnostic features of Conulariinae (continuation of the transverse ornament across the corner sulcus and lack of carinae) and Ctenoconulariinae ( presence of carinae) are symplesiomorphic or homoplastic, and Paraconulariinae is polyphyletic. The families Conulariellidae Kiderlen, 1937 and Conulariopsidae Sugiyama, 1942, also recognized in the TIP, are monogeneric, and since they provide no additional phylogenetic information, should be abandoned.

The identity of Mygale brunnipes CL Koch 1842 (Araneae, Theraphosidae), with a redescription of the species and the description of a new genus

We describe Kochiana new genus to accommodate a small Brazilian theraphosine species described originally as Mygale brunnipes by Koch (1842), resulting in Kochiana brunnipes new combination. Recently, specimens were rediscovered in northeastern Brazilian Atlantic rainforest. A preliminary cladistic analysis using equal weights parsimony and implied weights, was carried out to examine its phylogenetic placement. Kochiana new genus was monophyletic in all trees regardless of weighting scheme or concavity used. There is preliminary evidence for Kochiana new genus monophyly and weak evidence for its placement as sister group of Plesiopelma. Kochiana new genus can be characterized by the presence of a hornshaped spermatheca in females and males with a palpal bulb having prolateral accessory keels and a well developed medial crest on the embolus apex.

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.