Using sentinels to detect intersections of convex and nonconvex polygons

We describe finite sets of points, called sentinels, which allow us to decide if isometric copies of polygons, convex or not, intersect. As an example of the applicability of the concept of sentinel, we explain how they can be used to formulate an algorithm based on the optimization of differentiable models to pack polygons in convex sets. Mathematical subject classification: 90C53, 65K05.

Improving the tracking capability of adaptive filters via convex combination

As is well known, Hessian-based adaptive filters (such as the recursive-least squares algorithm (RLS) for supervised adaptive filtering, or the Shalvi-Weinstein algorithm (SWA) for blind equalization) converge much faster than gradient-based algorithms [such as the least-mean-squares algorithm (LMS) or the constant-modulus algorithm (CMA)]. However, when the problem is tracking a time-variant filter, the issue is not so clear-cut: there are environments for which each family presents better performance. Given this, we propose the use of a convex combination of algorithms of different families to obtain an algorithm with superior tracking capability. We show the potential of this combination and provide a unified theoretical model for the steady-state excess mean-square error for convex combinations of gradient- and Hessian-based algorithms, assuming a random-walk model for the parameter variations. The proposed model is valid for algorithms of the same or different families, and for supervised (LMS and RLS) or blind (CMA and SWA) algorithms.

Orthogonal packing of identical rectangles within isotropic convex regions

A mixed integer continuous nonlinear model and a solution method for the problem of orthogonally packing identical rectangles within an arbitrary convex region are introduced in the present work. The convex region is assumed to be made of an isotropic material in such a way that arbitrary rotations of the items, preserving the orthogonality constraint, are allowed. The solution method is based on a combination of branch and bound and active-set strategies for bound-constrained minimization of smooth functions. Numerical results show the reliability of the presented approach. (C) 2010 Elsevier Ltd. All rights reserved.

Algorithms for Maximum Independent Set in Convex Bipartite Graphs

A bipartite graph G = (V, W, E) is convex if there exists an ordering of the vertices of W such that, for each v. V, the neighbors of v are consecutive in W. We describe both a sequential and a BSP/CGM algorithm to find a maximum independent set in a convex bipartite graph. The sequential algorithm improves over the running time of the previously known algorithm and the BSP/CGM algorithm is a parallel version of the sequential one. The complexity of the algorithms does not depend on |W|.

The C(K, X) spaces for compact metric spaces K and X with a uniformly convex maximal factor

In this paper, we prove that if a Banach space X contains some uniformly convex subspace in certain geometric position, then the C(K, X) spaces of all X-valued continuous functions defined on the compact metric spaces K have exactly the same isomorphism classes that the C(K) spaces. This provides a vector-valued extension of classical results of Bessaga and Pelczynski (1960) [2] and Milutin (1966) [13] on the isomorphic classification of the separable C(K) spaces. As a consequence, we show that if 1 < p < q < infinity then for every infinite countable compact metric spaces K(1), K(2), K(3) and K(4) are equivalent: (a) C(K(1), l(p)) circle plus C(K(2), l(q)) is isomorphic to C(K(3), l(p)) circle plus (K(4), l(q)). (b) C(K(1)) is isomorphic to C(K(3)) and C(K(2)) is isomorphic to C(K(4)). (C) 2011 Elsevier Inc. All rights reserved.

Configurações centrais planares do tipo pipa

Neste artigo estudamos configurações centrais planares do tipo pipa para o problema de quatro corpos. Mostramos a existência de tais configurações para as pipas côncavas, quando uma das massas está no interior do triângulo formado pelas outras três massas, e para as pipas convexas, quando uma das massas está no exterior do triângulo formado pelas outras três massas.

Metapyrophorus pharolim a new genus and species of Pyrophorini (Coleoptera, Elateridae, Agrypninae)

Metapyrophorus, a new monotypic genus, is erected based on M. pharolim, new species from Trinidad and Tobago and Venezuela. The genus is characterized mainly by its pair of convex pronotal bioluminescent organs, equidistant between the median line and the lateral margin.

Characterization of subgraph relationships and distribution in complex networks

A network can be analyzed at different topological scales, ranging from single nodes to motifs, communities, up to the complete structure. We propose a novel approach which extends from single nodes to the whole network level by considering non-overlapping subgraphs (i.e. connected components) and their interrelationships and distribution through the network. Though such subgraphs can be completely general, our methodology focuses on the cases in which the nodes of these subgraphs share some special feature, such as being critical for the proper operation of the network. The methodology of subgraph characterization involves two main aspects: (i) the generation of histograms of subgraph sizes and distances between subgraphs and (ii) a merging algorithm, developed to assess the relevance of nodes outside subgraphs by progressively merging subgraphs until the whole network is covered. The latter procedure complements the histograms by taking into account the nodes lying between subgraphs, as well as the relevance of these nodes to the overall subgraph interconnectivity. Experiments were carried out using four types of network models and five instances of real-world networks, in order to illustrate how subgraph characterization can help complementing complex network-based studies.

Dihadron azimuthal correlations in Au+Au collisions at root s(NN)=200 GeV

Azimuthal angle (Delta phi) correlations are presented for a broad range of transverse momentum (0.4 < p(T) < 10 GeV/c) and centrality (0-92%) selections for charged hadrons from dijets in Au+Au collisions at root s(NN) = 200 GeV. With increasing p(T), the away-side Delta phi distribution evolves from a broad and relatively flat shape to a concave shape, then to a convex shape. Comparisons with p + p data suggest that the away-side distribution can be divided into a partially suppressed ""head"" region centered at Delta phi similar to pi, and an enhanced ""shoulder"" region centered at Delta phi similar to pi +/- 1.1. The p(T) spectrum for the associated hadrons in the head region softens toward central collisions. The spectral slope for the shoulder region is independent of centrality and trigger p(T). The properties of the near-side distributions are also modified relative to those in p + p collisions, reflected by the broadening of the jet shape in Delta phi and Delta eta, and an enhancement of the per-trigger yield. However, these modifications seem to be limited to p(T)less than or similar to 4 GeV/c, above which both the hadron pair shape and per-trigger yield become similar to p + p collisions. These observations suggest that both the away- and near-side distributions contain a jet fragmentation component which dominates for p(T) greater than or similar to 5 GeV/c and a medium-induced component which is important for p(T) less than or similar to 4 GeV/c. We also quantify the role of jets at intermediate and low p(T) through the yield of jet-induced pairs in comparison with binary scaled p + p pair yield. The yield of jet-induced pairs is suppressed at high pair proxy energy (sum of the p(T) magnitudes of the two hadrons) and is enhanced at low pair proxy energy. The former is consistent with jet quenching; the latter is consistent with the enhancement of soft hadron pairs due to transport of lost energy to lower p(T).

Transverse momentum and centrality dependence of dihadron correlations in Au plus Au collisions at root s(NN)=200 GeV: Jet quenching and the response of partonic matter

Azimuthal angle (Delta phi) correlations are presented for charged hadrons from dijets for 0.4 < p(T)< 10 GeV/c in Au+Au collisions at root s(NN)=200 GeV. With increasing p(T), the away-side distribution evolves from a broad and relatively flat shape to a concave shape, then to a convex shape. Comparisons to p+p data suggest that the away-side can be divided into a partially suppressed ""head"" region centered at Delta phi similar to pi and an enhanced ""shoulder"" region centered at Delta phi similar to pi +/- 1.1. The p(T) spectrum for the head region softens toward central collisions, consistent with the onset of jet quenching. The spectral slope for the shoulder region is independent of centrality and trigger p(T), which offers constraints on energy transport mechanisms and suggests that it contains the medium response to energetic jets.

On the k-restricted structure ratio in planar and outerplanar graphs

A planar k-restricted structure is a simple graph whose blocks are planar and each has at most k vertices. Planar k-restricted structures are used by approximation algorithms for Maximum Weight Planar Subgraph, which motivates this work. The planar k-restricted ratio is the infimum, over simple planar graphs H, of the ratio of the number of edges in a maximum k-restricted structure subgraph of H to the number edges of H. We prove that, as k tends to infinity, the planar k-restricted ratio tends to 1/2. The same result holds for the weighted version. Our results are based on analyzing the analogous ratios for outerplanar and weighted outerplanar graphs. Here both ratios tend to 1 as k goes to infinity, and we provide good estimates of the rates of convergence, showing that they differ in the weighted from the unweighted case.

INFERENCE FOR EIGENVALUES AND EIGENVECTORS OF GAUSSIAN SYMMETRIC MATRICES

This article presents maximum likelihood estimators (MLEs) and log-likelihood ratio (LLR) tests for the eigenvalues and eigenvectors of Gaussian random symmetric matrices of arbitrary dimension, where the observations are independent repeated samples from one or two populations. These inference problems are relevant in the analysis of diffusion tensor imaging data and polarized cosmic background radiation data, where the observations are, respectively, 3 x 3 and 2 x 2 symmetric positive definite matrices. The parameter sets involved in the inference problems for eigenvalues and eigenvectors are subsets of Euclidean space that are either affine subspaces, embedded submanifolds that are invariant under orthogonal transformations or polyhedral convex cones. We show that for a class of sets that includes the ones considered in this paper, the MLEs of the mean parameter do not depend on the covariance parameters if and only if the covariance structure is orthogonally invariant. Closed-form expressions for the MLEs and the associated LLRs are derived for this covariance structure.

An algorithmic Friedman-Pippenger theorem on tree embeddings and applications

An (n, d)-expander is a graph G = (V, E) such that for every X subset of V with vertical bar X vertical bar <= 2n - 2 we have vertical bar Gamma(G)(X) vertical bar >= (d + 1) vertical bar X vertical bar. A tree T is small if it has at most n vertices and has maximum degree at most d. Friedman and Pippenger (1987) proved that any ( n; d)- expander contains every small tree. However, their elegant proof does not seem to yield an efficient algorithm for obtaining the tree. In this paper, we give an alternative result that does admit a polynomial time algorithm for finding the immersion of any small tree in subgraphs G of (N, D, lambda)-graphs Lambda, as long as G contains a positive fraction of the edges of Lambda and lambda/D is small enough. In several applications of the Friedman-Pippenger theorem, including the ones in the original paper of those authors, the (n, d)-expander G is a subgraph of an (N, D, lambda)-graph as above. Therefore, our result suffices to provide efficient algorithms for such previously non-constructive applications. As an example, we discuss a recent result of Alon, Krivelevich, and Sudakov (2007) concerning embedding nearly spanning bounded degree trees, the proof of which makes use of the Friedman-Pippenger theorem. We shall also show a construction inspired on Wigderson-Zuckerman expander graphs for which any sufficiently dense subgraph contains all trees of sizes and maximum degrees achieving essentially optimal parameters. Our algorithmic approach is based on a reduction of the tree embedding problem to a certain on-line matching problem for bipartite graphs, solved by Aggarwal et al. (1996).

ON THE THREE-DIMENSIONAL BLASCHKE-LEBESGUE PROBLEM

The width of a closed convex subset of n-dimensional Euclidean space is the distance between two parallel supporting hyperplanes. The Blaschke-Lebesgue problem consists of minimizing the volume in the class of convex sets of fixed constant width and is still open in dimension n >= 3. In this paper we describe a necessary condition that the minimizer of the Blaschke-Lebesgue must satisfy in dimension n = 3: we prove that the smooth components of the boundary of the minimizer have their smaller principal curvature constant and therefore are either spherical caps or pieces of tubes (canal surfaces).

Coexistence of forest and savanna in an Amazonian area from a geological perspective

Question: How can the coexistence of savanna and forest in Amazonian areas with relatively uniform climates be explained? Location: Eastern Marajo Island, northeast Amazonia, Brazil. Methods: The study integrated floristic analysis, terrain morphology, sedimentology and delta(13)C of soil organic matter. Floristic analysis involved rapid ecological assessment of 33 sites, determination of occurrence, specific richness, hierarchical distribution and matrix of floristic similarity between paired vegetation types. Terrain characterization was based on analysis of Landsat images using 4(R), 5(G) and 7(B) composition and digital elevation model (DEM). Sedimentology involved field descriptions of surface and core sediments. Finally, radiocarbon dating and analysis of delta(13)C of soil profile organic matter and natural ecotone forest-savanna was undertaken. Results: Slight tectonic subsidence in eastern Marajo Island favours seasonal flooding, making it unsuitable for forest growth. However, this area displays slightly convex-up, sinuous morphologies related to paleochannels, covered by forest. Terra-firme lowland forests are expanding from west to east, preferentially occupying paleochannels and replacing savanna. Slack, running water during channel abandonment leads to disappearance of varzea/gallery forest at channel margins. Long-abandoned channels sustain continuous terra-firme forests, because of longer times for more species to establish. Recently abandoned channels have had less time to become sites for widespread tree development, and are either not vegetated or covered by savanna. Conclusion: Landforms in eastern Marajo Island reflect changes in the physical environment due to reactivation of tectonic faults during the latest Quaternary. This promoted a dynamic history of channel abandonment, which controlled a set of interrelated parameters (soil type, topography, hydrology) that determined species location. Inclusion of a geological perspective for paleoenvironmental reconstruction can increase understanding of plant distribution in Amazonia.