Dynamic data structures for fat objects and their applications

We present several efficient dynamic data structures for point-enclosure queries, involving convex fat objects in or . Our planar structures are actually fitted for a more general class of objects – (β,δ)-covered objects – which are not necessarily convex, see definition below. These structures are more efficient than alternative known structures, because they exploit the fatness of the objects. We then apply these structures to obtain efficient solutions to two problems: (i) finding a perfect containment matching between a set of points and a set of convex fat objects, and (ii) finding a piercing set for a collection of convex fat objects, whose size is optimal up to some constant factor.     

The longest cycle of a graph with a large minimal degree

We show that every graph G on n vertices with minimal degree at least n/k contains a cycle of length at least [n/(k ? 1)]. This verifies a conjecture of Katchalski. When k = 2 our result reduces to the classical theorem of Dirac that asserts that if all degrees are at least 1/2n then G is Hamiltonian.     

On the performance of the ICP algorithm

We present upper and lower bounds for the number of iterations performed by the Iterative Closest Point (ICP) algorithm. This algorithm has been proposed by Besl and McKay as a successful heuristic for matching of point sets in d-space under translation, but so far it seems not to have been rigorously analyzed. We consider two standard measures of resemblance that the algorithm attempts to optimize: The RMS (root mean squared distance) and the (one-sided) Hausdorff distance. We show that in both cases the number of iterations performed by the algorithm is polynomial in the number of input points. In particular, this bound is quadratic in the one-dimensional problem, under the RMS measure, for which we present a lower bound construction of Ω(nlogn) iterations, where n is the overall size of the input. Under the Hausdorff measure, this bound is only O(n) for input point sets whose spread is polynomial in n, and this is tight in the worst case.We also present several structural geometric properties of the algorithm under both measures. For the RMS measure, we show that at each iteration of the algorithm the cost function monotonically and strictly decreases along the vector Δt of the relative translation. As a result, we conclude that the polygonal path π, obtained by concatenating all the relative translations that are computed during the execution of the algorithm, does not intersect itself. In particular, in the one-dimensional problem all the relative translations of the ICP algorithm are in the same (left or right) direction. For the Hausdorff measure, some of these properties continue to hold (such as monotonicity in one dimension), whereas others do not.     

On the maximum number of Hamiltonian paths in tournaments

By using the probabilistic method, we show that the maximum number of directed Hamiltonian paths in a complete directed graph with n vertices is at least (e?o(1)) (n!/2^n?1). © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 291–296, 2001     

Search for a standard model Higgs boson in the H→ZZ→ℓ(+)ℓ(-)νν decay channel with the ATLAS detector

A search for a heavy standard model Higgs boson decaying via H→ZZ→→?(+)?(-)νν, where ?=e, μ, is presented. It is based on proton-proton collision data at √s=7 TeV, collected by the ATLAS experiment at the LHC in the first half of 2011 and corresponding to an integrated luminosity of 1.04 fb(-1). The data are compared to the expected standard model backgrounds. The data and the background expectations are found to be in agreement and upper limits are placed on the Higgs boson production cross section over the entire mass window considered; in particular, the production of a standard model Higgs boson is excluded in the region 340相似文献   

Classification of heterotic Pati–Salam models

We extend the classification of free fermionic heterotic-string models to vacua in which the SO(10)$\mathit{SO}(10)$ GUT symmetry is broken at the string level to the Pati–Salam subgroup. Using our classification method we recently presented the first example of a quasi-realistic heterotic-string vacuum that is free of massless exotic states. Within this method we are able to derive algebraic expressions for the Generalised GSO (GGSO) projections for all sectors that appear in the models. This facilitates the programming of the entire spectrum analysis in a computer code. The total number of vacua in the class of models that we classify is ²⁵¹∼¹⁰¹⁵$2^{51}\sim {10}^{15}$. We perform a statistical sampling in this space of models and extract 10¹¹ GGSO configurations with Pati–Salam gauge group. Our results demonstrate that one in every 10⁶ vacua correspond to a three generation exophobic model with the required Higgs states, needed to induce spontaneous breaking to the Standard Model.