Algorithms for Geometric Matching, Clustering, and Covering

With the popularization of GPS-enabled devices such as mobile phones, location data are becoming available at an unprecedented scale. The locations may be collected from many different sources such as vehicles moving around a city, user check-ins in social networks, and geo-tagged micro-blogging photos or messages. Besides the longitude and latitude, each location record may also have a timestamp and additional information such as the name of the location. Time-ordered sequences of these locations form trajectories, which together contain useful high-level information about people's movement patterns.

The first part of this thesis focuses on a few geometric problems motivated by the matching and clustering of trajectories. We first give a new algorithm for computing a matching between a pair of curves under existing models such as dynamic time warping (DTW). The algorithm is more efficient than standard dynamic programming algorithms both theoretically and practically. We then propose a new matching model for trajectories that avoids the drawbacks of existing models. For trajectory clustering, we present an algorithm that computes clusters of subtrajectories, which correspond to common movement patterns. We also consider trajectories of check-ins, and propose a statistical generative model, which identifies check-in clusters as well as the transition patterns between the clusters.

The second part of the thesis considers the problem of covering shortest paths in a road network, motivated by an EV charging station placement problem. More specifically, a subset of vertices in the road network are selected to place charging stations so that every shortest path contains enough charging stations and can be traveled by an EV without draining the battery. We first introduce a general technique for the geometric set cover problem. This technique leads to near-linear-time approximation algorithms, which are the state-of-the-art algorithms for this problem in either running time or approximation ratio. We then use this technique to develop a near-linear-time algorithm for this

shortest-path cover problem.

An Eulerian Immersed Boundary Method for flow simulations over stationary and moving rigid bodies

The fluid flow over bodies with complex geometry has been the subject of research of many scientists and widely explored experimentally and numerically. The present study proposes an Eulerian Immersed Boundary Method for flows simulations over stationary or moving rigid bodies. The proposed method allows the use of Cartesians Meshes. Here, two-dimensional simulations of fluid flow over stationary and oscillating circular cylinders were used for verification and validation. Four different cases were explored: the flow over a stationary cylinder, the flow over a cylinder oscillating in the flow direction, the flow over a cylinder oscillating in the normal flow direction, and a cylinder with angular oscillation. The time integration was carried out by a classical 4th order Runge-Kutta scheme, with a time step of the same order of distance between two consecutive points in x direction. High-order compact finite difference schemes were used to calculate spatial derivatives. The drag and lift coefficients, the lock-in phenomenon and vorticity contour plots were used for the verification and validation of the proposed method. The extension of the current method allowing the study of a body with different geometry and three-dimensional simulations is straightforward. The results obtained show a good agreement with both numerical and experimental results, encouraging the use of the proposed method.

Preliminary studies of laser-induced breakdown spectrometry for the determination of Ba, Cd, Cr and Pb in toys

The performance of laser-induced breakdown spectrometry (LIBS) for the determination of Ba, Cd, Cr and Pb in toys has been evaluated by using a Nd:YAG laser operating at 1064 nm and an Echelle spectrometer with intensified charge-coupled device detector. Samples were purchased in different cities of Sao Paulo State market and analyzed directly without sample preparation. Laser-induced breakdown spectrometry experimental conditions (number of pulses, delay time. integration time gate and pulse energy) were optimized by using a Doehlert design. Laser-induced breakdown spectrometry signals correlated reasonably well with inductively coupled plasma optical emission spectrometry (ICP OES) concentrations after microwave-assisted acid digestion of selected samples. Thermal analysis was used for polymer identification and scanning electron microscopy to Visualize differences in crater geometry of different polymers employed for toy fabrication. Results indicate that laser-induced breakdown spectrometry can be proposed as a rapid screening method for investigation of potentially toxic elements in toys. The unique application of laser-induced breakdown spectrometry for identification of contaminants in successive layers of ink and polymer is also demonstrated. (C) 2009 Elsevier B.V. All rights reserved.

An exact conserving algorithm for nonlinear dynamics with rotational DOFs and general hyperelasticity. Part 2: shells

Following the approach developed for rods in Part 1 of this paper (Pimenta et al. in Comput. Mech. 42:715-732, 2008), this work presents a fully conserving algorithm for the integration of the equations of motion in nonlinear shell dynamics. We begin with a re-parameterization of the rotation field in terms of the so-called Rodrigues rotation vector, allowing for an extremely simple update of the rotational variables within the scheme. The weak form is constructed via non-orthogonal projection, the time-collocation of which ensures exact conservation of momentum and total energy in the absence of external forces. Appealing is the fact that general hyperelastic materials (and not only materials with quadratic potentials) are permitted in a totally consistent way. Spatial discretization is performed using the finite element method and the robust performance of the scheme is demonstrated by means of numerical examples.

An exact conserving algorithm for nonlinear dynamics with rotational DOFs and general hyperelasticity. Part 1: Rods

A fully conserving algorithm is developed in this paper for the integration of the equations of motion in nonlinear rod dynamics. The starting point is a re-parameterization of the rotation field in terms of the so-called Rodrigues rotation vector, which results in an extremely simple update of the rotational variables. The weak form is constructed with a non-orthogonal projection corresponding to the application of the virtual power theorem. Together with an appropriate time-collocation, it ensures exact conservation of momentum and total energy in the absence of external forces. Appealing is the fact that nonlinear hyperelastic materials (and not only materials with quadratic potentials) are permitted without any prejudice on the conservation properties. Spatial discretization is performed via the finite element method and the performance of the scheme is assessed by means of several numerical simulations.

Large amplitude folding in finely layered viscoelastic rock structures

We analyze folding phenomena in finely layered viscoelastic rock. Fine is meant in the sense that the thickness of each layer is considerably smaller than characteristic structural dimensions. For this purpose we derive constitutive relations and apply a computational simulation scheme (a finite-element based particle advection scheme; see MORESI et al., 2001) suitable for problems involving very large deformations of layered viscous and viscoelastic rocks. An algorithm for the time integration of the governing equations as well as details of the finite-element implementation is also given. We then consider buckling instabilities in a finite, rectangular domain. Embedded within this domain, parallel to the longer dimension we consider a stiff, layered plate. The domain is compressed along the layer axis by prescribing velocities along the sides. First, for the viscous limit we consider the response to a series of harmonic perturbations of the director orientation. The Fourier spectra of the initial folding velocity are compared for different viscosity ratios. Turning to the nonlinear regime we analyze viscoelastic folding histories up to 40% shortening. The effect of layering manifests itself in that appreciable buckling instabilities are obtained at much lower viscosity ratios (1:10) as is required for the buckling of isotropic plates (1:500). The wavelength induced by the initial harmonic perturbation of the director orientation seems to be persistent. In the section of the parameter space considered here elasticity seems to delay or inhibit the occurrence of a second, larger wavelength. Finally, in a linear instability analysis we undertake a brief excursion into the potential role of couple stresses on the folding process. The linear instability analysis also provides insight into the expected modes of deformation at the onset of instability, and the different regimes of behavior one might expect to observe.

Sistema de multiprocessamento para simulação de N-corpos em FPGA

Trabalho Final de Mestrado para obtenção do grau de Mestre em Engenharia de Electrónica e Telecomunicações

Post-processing Techniques in Free Boundary Flows during Liquid Composite Moulding Processes

Post-processing a finite element solution is a well-known technique, which consists in a recalculation of the originally obtained quantities such that the rate of convergence increases without the need for expensive remeshing techniques. Postprocessing is especially effective in problems where better accuracy is required for derivatives of nodal variables in regions where Dirichlet essential boundary condition is imposed strongly. Consequently such an approach can be exceptionally good in modelling of resin infiltration under quasi steady-state assumption by remeshing techniques and with explicit time integration, because only the free-front normal velocities are necessary to advance the resin front to the next position. The new contribution is the post-processing analysis and implementation of the freeboundary velocities of mesolevel infiltration analysis. Such implementation ensures better accuracy on even coarser meshes, which in consequence reduces the computational time also by the possibility of employing larger time steps.

An optimal boundary fair scheduling

Nowadays, many real-time operating systems discretize the time relying on a system time unit. To take this behavior into account, real-time scheduling algorithms must adopt a discrete-time model in which both timing requirements of tasks and their time allocations have to be integer multiples of the system time unit. That is, tasks cannot be executed for less than one time unit, which implies that they always have to achieve a minimum amount of work before they can be preempted. Assuming such a discrete-time model, the authors of Zhu et al. (Proceedings of the 24th IEEE international real-time systems symposium (RTSS 2003), 2003, J Parallel Distrib Comput 71(10):1411–1425, 2011) proposed an efficient “boundary fair” algorithm (named BF) and proved its optimality for the scheduling of periodic tasks while achieving full system utilization. However, BF cannot handle sporadic tasks due to their inherent irregular and unpredictable job release patterns. In this paper, we propose an optimal boundary-fair scheduling algorithm for sporadic tasks (named BF TeX ), which follows the same principle as BF by making scheduling decisions only at the job arrival times and (expected) task deadlines. This new algorithm was implemented in Linux and we show through experiments conducted upon a multicore machine that BF TeX outperforms the state-of-the-art discrete-time optimal scheduler (PD TeX ), benefiting from much less scheduling overheads. Furthermore, it appears from these experimental results that BF TeX is barely dependent on the length of the system time unit while PD TeX —the only other existing solution for the scheduling of sporadic tasks in discrete-time systems—sees its number of preemptions, migrations and the time spent to take scheduling decisions increasing linearly when improving the time resolution of the system.

GVSOS: A New Client for OGC SOS Interface Standard

Dissertation submitted in partial fulfillment of the requirements for the Degree of Master of Science in Geospatial Technologies.

Numerical Assessment of the out-of-plane response of a brick masonry structure without box behaviour

This paper presents the assessment of the out-of-plane response due to seismic loading of a masonry structure without rigid diaphragm. This structure corresponds to real scale brick masonry specimen with a main façade connected to two return walls. Two modelling approaches were defined for this evaluation. The first one consisted on macro modelling, whereas the second one on simplified micro modelling. As a first step of this study, static nonlinear analyses were conducted to the macro model aiming at evaluating the out-of-plane response and failure mechanism of the masonry structure. A sensibility analyses was performed in order to assess the mesh size and material model dependency. In addition, the macro models were subjected to dynamic nonlinear analyses with time integration in order to assess the collapse mechanism. Finally, these analyses were also applied to a simplified micro model of the masonry structure. Furthermore, these results were compared to experimental response from shaking table tests. It was observed that these numerical techniques simulate correctly the in-plane behaviour of masonry structures. However, the

Seismic vulnerability of existing masonry buildings: Nonlinear parametric analysis

Existing masonry structures are usually associated to a high seismic vulnerability, mainly due to the properties of the materials, weak connections between floors and load-bearing walls, high mass of the masonry walls and flexibility of the floors. For these reasons, the seismic performance of existing masonry structures has received much attention in the last decades. This study presents the parametric analysis taking into account the deviations on features of the gaioleiro buildings - Portuguese building typology. The main objective of the parametric analysis is to compare the seismic performance of the structure as a function of the variations of its properties with respect to the response of a reference model. The parametric analysis was carried out for two types of structural analysis, namely for the non-linear dynamic analysis with time integration and for the pushover analysis with distribution of forces proportional to the inertial forces of the structure. The Young's modulus of the masonry walls, Young's modulus of the timber floors, the compressive and tensile non-linear properties (strength and fracture energy) were the properties considered in both type of analysis. Additionally, in the dynamic analysis, the influences of the vis-cous damping and of the vertical component of the earthquake were evaluated. A pushover analysis proportional to the modal displacement of the first mode in each direction was also carried out. The results shows that the Young's modulus of the masonry walls, the Young's modulus of the timber floors and the compressive non-linear properties are the pa-rameters that most influence the seismic performance of this type of tall and weak existing masonry structures. Furthermore, it is concluded that that the stiffness of the floors influences significantly the strength capacity and the collapse mecha-nism of the numerical model. Thus, a study on the strengthening of the floors was also carried out. The increase of the thickness of the timber floors was the strengthening technique that presented the best seismic performance, in which the reduction of the out-of-plane displacements of the masonry walls is highlighted.

North-South trade and directed technical change

In a world where poor countries provide weak protection for intellectual property rights (IPRs), market integration shifts technical change in favor of rich nations. Through this channel, free trade may amplify international income differences. At the same time, integration with countries where IPRs are weakly protected can slow down the world growth rate. An important implication of these results is that protection of intellectual property is most beneficial in open countries. This prediction, which is novel in the literature, is consistent with evidence from a panel of 53 countries observed in the years 1965-1990. The paper also provides empirical support for the mechanism linking North-South trade to the direction of technical change: an increase in import penetration from low-wage, low-IPRs, countries is followed by a sharp fall in R&D investment in a panel of US manufacturing sectors.

An objective anisotropic elastic plastic model and Algorithm applicable to bone mechanics

The implicit projection algorithm of isotropic plasticity is extended to an objective anisotropic elastic perfectly plastic model. The recursion formula developed to project the trial stress on the yield surface, is applicable to any non linear elastic law and any plastic yield function.A curvilinear transverse isotropic model based on a quadratic elastic potential and on Hill's quadratic yield criterion is then developed and implemented in a computer program for bone mechanics perspectives. The paper concludes with a numerical study of a schematic bone-prosthesis system to illustrate the potential of the model.