Preconditioning 2D Integer Data for Fast Convex Hull Computations

In order to accelerate computing the convex hull on a set of n points, a heuristic procedure is often applied to reduce the number of points to a set of s points, s ≤ n, which also contains the same hull. We present an algorithm to precondition 2D data with integer coordinates bounded by a box of size p × q before building a 2D convex hull, with three distinct advantages. First, we prove that under the condition min(p, q) ≤ n the algorithm executes in time within O(n); second, no explicit sorting of data is required; and third, the reduced set of s points forms a simple polygonal chain and thus can be directly pipelined into an O(n) time convex hull algorithm. This paper empirically evaluates and quantifies the speed up gained by preconditioning a set of points by a method based on the proposed algorithm before using common convex hull algorithms to build the final hull. A speedup factor of at least four is consistently found from experiments on various datasets when the condition min(p, q) ≤ n holds; the smaller the ratio min(p, q)/n is in the dataset, the greater the speedup factor achieved.

Efficient aggregate computations in large-scale dense WSN

We focus on large-scale and dense deeply embedded systems where, due to the large amount of information generated by all nodes, even simple aggregate computations such as the minimum value (MIN) of the sensor readings become notoriously expensive to obtain. Recent research has exploited a dominance-based medium access control(MAC) protocol, the CAN bus, for computing aggregated quantities in wired systems. For example, MIN can be computed efficiently and an interpolation function which approximates sensor data in an area can be obtained efficiently as well. Dominance-based MAC protocols have recently been proposed for wireless channels and these protocols can be expected to be used for achieving highly scalable aggregate computations in wireless systems. But no experimental demonstration is currently available in the research literature. In this paper, we demonstrate that highly scalable aggregate computations in wireless networks are possible. We do so by (i) building a new wireless hardware platform with appropriate characteristics for making dominance-based MAC protocols efficient, (ii) implementing dominance-based MAC protocols on this platform, (iii) implementing distributed algorithms for aggregate computations (MIN, MAX, Interpolation) using the new implementation of the dominance-based MAC protocol and (iv) performing experiments to prove that such highly scalable aggregate computations in wireless networks are possible.

Reliable and Fast Hand-Offs in Low-Power Wireless Networks

Hand-off (or hand-over), the process where mobile nodes select the best access point available to transfer data, has been well studied in wireless networks. The performance of a hand-off process depends on the specific characteristics of the wireless links. In the case of low-power wireless networks, hand-off decisions must be carefully taken by considering the unique properties of inexpensive low-power radios. This paper addresses the design, implementation and evaluation of smart-HOP, a hand-off mechanism tailored for low-power wireless networks. This work has three main contributions. First, it formulates the hard hand-off process for low-power networks (such as typical wireless sensor networks - WSNs) with a probabilistic model, to investigate the impact of the most relevant channel parameters through an analytical approach. Second, it confirms the probabilistic model through simulation and further elaborates on the impact of several hand-off parameters. Third, it fine-tunes the most relevant hand-off parameters via an extended set of experiments, in a realistic experimental scenario. The evaluation shows that smart-HOP performs well in the transitional region while achieving more than 98 percent relative delivery ratio and hand-off delays in the order of a few tens of a milliseconds.

Doppler ultrasound - a valid and reliable tool to assess spondyloarthritis

Enthesitis is the hallmark of spondyloarthritis and is observed in all subtypes. Namely, a wide information on spondyloarthritis abnormalities, including synovitis, bursitis, tendinitis, enthesitis and cortical bone abnormalities (erosions and enthesophytes), can be efficiently perceived by ultrasound power Doppler. Furthermore, several studies on imaging of enthesis showed that imaging techniques are better than clinical examination to detect pathology at asymptomatic enthesis. Vascularized enthesitis detected by ultrasound power Doppler appears to be a valuable diagnostic tool to confirm spondyloarthritis diagnosis. This article focuses on the validity and reliability of ultrasound enthesitis assessment in the management of spondyloarthritis patients.

How reliable is the monitoring of permanent vegetation plots? A test with multiple observers

Questions: A multiple plot design was developed for permanent vegetation plots. How reliable are the different methods used in this design and which changes can we measure? Location: Alpine meadows (2430 m a.s.l.) in the Swiss Alps. Methods: Four inventories were obtained from 40 m(2) plots: four subplots (0.4 m(2)) with a list of species, two 10m transects with the point method (50 points on each), one subplot (4 m2) with a list of species and visual cover estimates as a percentage and the complete plot (40 m(2)) with a list of species and visual estimates in classes. This design was tested by five to seven experienced botanists in three plots. Results: Whatever the sampling size, only 45-63% of the species were seen by all the observers. However, the majority of the overlooked species had cover < 0.1%. Pairs of observers overlooked 10-20% less species than single observers. The point method was the best method for cover estimate, but it took much longer than visual cover estimates, and 100 points allowed for the monitoring of only a very limited number of species. The visual estimate as a percentage was more precise than classes. Working in pairs did not improve the estimates, but one botanist repeating the survey is more reliable than a succession of different observers. Conclusion: Lists of species are insufficient for monitoring. It is necessary to add cover estimates to allow for subsequent interpretations in spite of the overlooked species. The choice of the method depends on the available resources: the point method is time consuming but gives precise data for a limited number of species, while visual estimates are quick but allow for recording only large changes in cover. Constant pairs of observers improve the reliability of the records.

Using the Reliable Change Index Statistic to Analyze Developmental Changes in Infants at Risk for Autism Spectrum Disorder

Longitudinal studies of the development of autism spectrum disorders (ASD) provide an understanding of which variables may be important predictors of an ASD. The objective of the current study is to apply the reliable change index (RCI) statistic to examine whether the Parent Observation of Early Markers Scale (POEMS) is sensitive to developmental change, and whether these changes can be quantified along a child’s developmental trajectory. Ninety-six children with older siblings with autism were followed from 1-36 months of age. Group-based RCI analysis confirms that the POEMS is capable of detecting significant changes within pre-defined diagnostic groups. Within-subject analysis suggests that ongoing monitoring of a child at-risk for an ASD requires interpretation of both significant intervals identified by the RCI statistic, as well as the presence of repeated high (i.e., >70) scores. This study provides preliminary evidence for a reasonably sensitive and specific means by which individual change can be clinically monitored via parent report.

Reliable computation for geometric models

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Reliable Solid Modelling Using Subdivision Surfaces

Les surfaces de subdivision fournissent une méthode alternative prometteuse dans la modélisation géométrique, et ont des avantages sur la représentation classique de trimmed-NURBS, en particulier dans la modélisation de surfaces lisses par morceaux. Dans ce mémoire, nous considérons le problème des opérations géométriques sur les surfaces de subdivision, avec l'exigence stricte de forme topologique correcte. Puisque ce problème peut être mal conditionné, nous proposons une approche pour la gestion de l'incertitude qui existe dans le calcul géométrique. Nous exigeons l'exactitude des informations topologiques lorsque l'on considère la nature de robustesse du problème des opérations géométriques sur les modèles de solides, et il devient clair que le problème peut être mal conditionné en présence de l'incertitude qui est omniprésente dans les données. Nous proposons donc une approche interactive de gestion de l'incertitude des opérations géométriques, dans le cadre d'un calcul basé sur la norme IEEE arithmétique et la modélisation en surfaces de subdivision. Un algorithme pour le problème planar-cut est alors présenté qui a comme but de satisfaire à l'exigence topologique mentionnée ci-dessus.

Méthodes numériques pour la capture et la résolution des discontinuités dans les solutions des systèmes hyperboliques

Réalisé en majeure partie sous la tutelle de feu le Professeur Paul Arminjon. Après sa disparition, le Docteur Aziz Madrane a pris la relève de la direction de mes travaux.

Reliable and Damage-Free Estimation of Resistivity of ZnO Thin Films for Photovoltaic Applications Using Photoluminescence Technique

This work projects photoluminescence (PL) as an alternative technique to estimate the order of resistivity of zinc oxide (ZnO) thin films. ZnO thin films, deposited using chemical spray pyrolysis (CSP) by varying the deposition parameters like solvent, spray rate, pH of precursor, and so forth, have been used for this study. Variation in the deposition conditions has tremendous impact on the luminescence properties as well as resistivity. Two emissions could be recorded for all samples—the near band edge emission (NBE) at 380 nm and the deep level emission (DLE) at ∼500 nm which are competing in nature. It is observed that the ratio of intensities of DLE to NBE ( DLE/ NBE) can be reduced by controlling oxygen incorporation in the sample. - measurements indicate that restricting oxygen incorporation reduces resistivity considerably. Variation of DLE/ NBE and resistivity for samples prepared under different deposition conditions is similar in nature. DLE/ NBE was always less than resistivity by an order for all samples.Thus from PL measurements alone, the order of resistivity of the samples can be estimated.

Computations in Relative Algebraic K-Groups

Let G be finite group and K a number field or a p-adic field with ring of integers O_K. In the first part of the manuscript we present an algorithm that computes the relative algebraic K-group K_0(O_K[G],K) as an abstract abelian group. We solve the discrete logarithm problem, both in K_0(O_K[G],K) and the locally free class group cl(O_K[G]). All algorithms have been implemented in MAGMA for the case K = \IQ. In the second part of the manuscript we prove formulae for the torsion subgroup of K_0(\IZ[G],\IQ) for large classes of dihedral and quaternion groups.