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.

Mixtures of g-priors in Generalized Linear Models

Mixtures of Zellner's g-priors have been studied extensively in linear models and have been shown to have numerous desirable properties for Bayesian variable selection and model averaging. Several extensions of g-priors to Generalized Linear Models (GLMs) have been proposed in the literature; however, the choice of prior distribution of g and resulting properties for inference have received considerably less attention. In this paper, we extend mixtures of g-priors to GLMs by assigning the truncated Compound Confluent Hypergeometric (tCCH) distribution to 1/(1+g) and illustrate how this prior distribution encompasses several special cases of mixtures of g-priors in the literature, such as the Hyper-g, truncated Gamma, Beta-prime, and the Robust prior. Under an integrated Laplace approximation to the likelihood, the posterior distribution of 1/(1+g) is in turn a tCCH distribution, and approximate marginal likelihoods are thus available analytically. We discuss the local geometric properties of the g-prior in GLMs and show that specific choices of the hyper-parameters satisfy the various desiderata for model selection proposed by Bayarri et al, such as asymptotic model selection consistency, information consistency, intrinsic consistency, and measurement invariance. We also illustrate inference using these priors and contrast them to others in the literature via simulation and real examples.

n-Alkane content and compound-specific d13C values of soil samples, river samples, and marine surface samples

Southwestern Africa's coastal marine mudbelt, a prominent Holocene sediment package, provides a valuable archive for reconstructing terrestrial palaeoclimates on the adjacent continent. While the origin of terrestrial inorganic material has been intensively studied, the sources of terrigenous organic material deposited in the mudbelt are yet unclear. In this study, plant wax derived n-alkanes and their compound-specific d13C in soils, flood deposits and suspension loads from regional fluvial systems and marine sediments are analysed to characterize the origin of terrestrial organic material in the southwest African mudbelt. Soils from different biomes in the catchments of the Orange River and small west coast rivers show on average distinct n-alkane distributions and compound-specific d13C values reflecting biome-specific vegetation types, most notably the winter rainfall associated Fynbos Biome of the southwestern Cape. In the fluvial sediment samples from the Orange River, changes in the n-alkane distributions and compound-specific d13C compositions reveal an overprint by local vegetation along the river's course. The smaller west coast rivers show distinct signals, reflecting their small catchment areas and particular vegetation communities. Marine surface sediments spanning a transect from the northern mudbelt (29°S) to St. Helena Bay (33°S) reveal subtle, but spatially coherent, changes in n-alkane distributions and compound-specific d13C, indicating the influence of Orange River sediments in the northern mudbelt, the increasing importance of terrigenous input from the adjacent western coastal biomes in the central mudbelt, and contributions from the Fynbos Biome to the southern mudbelt. These findings indicate the different sources of terrestrial organic material deposited in the mudbelt, and highlight the potential the mudbelt has to preserve evidence of environmental change from the adjacent continent.

Digital geometric-sequence control technique for bidirectional dual active bridge DC-DC converters used in future electric vehicles

Bidirectional DC-DC converters are widely used in different applications such as energy storage systems, Electric Vehicles (EVs), UPS, etc. In particular, future EVs require bidirectional power flow in order to integrate energy storage units into smart grids. These bidirectional power converters provide Grid to Vehicle (V2G)/ Vehicle to Grid (G2V) power flow capability for future EVs. Generally, there are two control loops used for bidirectional DC-DC converters: The inner current loop and The outer loop. The control of DAB converters used in EVs are proved to be challenging due to the wide range of operating conditions and non-linear behavior of the converter. In this thesis, the precise mathematical model of the converter is derived and non-linear control schemes are proposed for the control system of bidirectional DC-DC converters based on the derived model. The proposed inner current control technique is developed based on a novel Geometric-Sequence Control (GSC) approach. The proposed control technique offers significantly improved performance as compared to one for conventional control approaches. The proposed technique utilizes a simple control algorithm which saves on the computational resources. Therefore, it has higher reliability, which is essential in this application. Although, the proposed control technique is based on the mathematical model of the converter, its robustness against parameter uncertainties is proven. Three different control modes for charging the traction batteries in EVs are investigated in this thesis: the voltage mode control, the current mode control, and the power mode control. The outer loop control is determined by each of the three control modes. The structure of the outer control loop provides the current reference for the inner current loop. Comprehensive computer simulations have been conducted in order to evaluate the performance of the proposed control methods. In addition, the proposed control have been verified on a 3.3 kW experimental prototype. Simulation and experimental results show the superior performance of the proposed control techniques over the conventional ones.

Level-resolved quantum statistical theory of electron capture into many-electron compound resonances in highly charged ions

The strong mixing of many-electron basis states in excited atoms and ions with open f shells results in very large numbers of complex, chaotic eigenstates that cannot be computed to any degree of accuracy. Describing the processes which involve such states requires the use of a statistical theory. Electron capture into these “compound resonances” leads to electron-ion recombination rates that are orders of magnitude greater than those of direct, radiative recombination and cannot be described by standard theories of dielectronic recombination. Previous statistical theories considered this as a two-electron capture process which populates a pair of single-particle orbitals, followed by “spreading” of the two-electron states into chaotically mixed eigenstates. This method is similar to a configuration-average approach because it neglects potentially important effects of spectator electrons and conservation of total angular momentum. In this work we develop a statistical theory which considers electron capture into “doorway” states with definite angular momentum obtained by the configuration interaction method. We apply this approach to electron recombination with W²⁰⁺, considering 2×10⁶ doorway states. Despite strong effects from the spectator electrons, we find that the results of the earlier theories largely hold. Finally, we extract the fluorescence yield (the probability of photoemission and hence recombination) by comparison with experiment.

Combining human perception and geometric restrictions for automatic pedestrian detection

[EN]Automatic detection systems do not perform as well as human observers, even on simple detection tasks. A potential solution to this problem is training vision systems on appropriate regions of interests (ROIs), in contrast to training on predefined and arbitrarily selected regions. Here we focus on detecting pedestrians in static scenes. Our aim is to answer the following question: Can automatic vision systems for pedestrian detection be improved by training them on perceptually-defined ROIs?

Geometric properties of 2-dimensional minimal surfaces in a sub-Riemannian manifold which models the Visual Cortex

In this paper we study the notion of degree forsubmanifolds embedded in an equiregular sub-Riemannian manifold and we provide the definition of their associated area functional. In this setting we prove that the Hausdorff dimension of a submanifold coincides with its degree, as stated by Gromov. Using these general definitions we compute the first variation for surfaces embedded in low dimensional manifolds and we obtain the partial differential equation associated to minimal surfaces. These minimal surfaces have several applications in the neurogeometry of the visual cortex.

Review of Geometric Design Criteria and Lighting Design Criteria, 1968

The investigations for this report were initiated in October, 1967, to perform the following: l. Review the current Iowa State Highway Commission roadway geometric design standards and criteria for conformance with national policies and recent research findings with special attention to high way safety. 2. Review the current Iowa State Highway Commission roadway lighting design standards and criteria for conformance with national policies and recent research findings with special attention to high way safety

Geometric versus Model Predictive Control based guidance algorithms for fixed-wing UAVs in the presence of very strong wind fields.

The recent years have witnessed increased development of small, autonomous fixed-wing Unmanned Aerial Vehicles (UAVs). In order to unlock widespread applicability of these platforms, they need to be capable of operating under a variety of environmental conditions. Due to their small size, low weight, and low speeds, they require the capability of coping with wind speeds that are approaching or even faster than the nominal airspeed. In this thesis, a nonlinear-geometric guidance strategy is presented, addressing this problem. More broadly, a methodology is proposed for the high-level control of non-holonomic unicycle-like vehicles in the presence of strong flowfields (e.g. winds, underwater currents) which may outreach the maximum vehicle speed. The proposed strategy guarantees convergence to a safe and stable vehicle configuration with respect to the flowfield, while preserving some tracking performance with respect to the target path. As an alternative approach, an algorithm based on Model Predictive Control (MPC) is developed, and a comparison between advantages and disadvantages of both approaches is drawn. Evaluations in simulations and a challenging real-world flight experiment in very windy conditions confirm the feasibility of the proposed guidance approach.

Geometric Hamiltonian formulation of a variational problem depending on the covariant acceleration

We consider a second-order variational problem depending on the covariant acceleration, which is related to the notion of Riemannian cubic polynomials. This problem and the corresponding optimal control problem are described in the context of higher order tangent bundles using geometric tools. The main tool, a presymplectic variant of Pontryagin’s maximum principle, allows us to study the dynamics of the control problem.

Algebro-Geometric Aspects of the Classical Yang-Baxter Equation

In this thesis we consider algebro-geometric aspects of the Classical Yang-Baxter Equation and the Generalised Classical Yang-Baxter Equation. In chapter one we present a method to construct solutions of the Generalised Classical Yang-Baxter Equation starting with certain sheaves of Lie algebras on algebraic curves. Furthermore we discuss a criterion to check unitarity of such solutions. In chapter two we consider the special class of solutions coming from sheaves of traceless endomorphisms of simple vector bundles on the nodal cubic curve. These solutions are quasi-trigonometric and we describe how they fit into the classification scheme of such solutions. Moreover, we describe a concrete formula for these solutions. In the third and final chapter we show that any unitary, rational solution of the Classical Yang-Baxter Equation can be obtained via the method of chapter one applied to a sheaf of Lie algebras on the cuspidal cubic curve.

The stochastic geometric machine model

This paper introduces the stochastic version of the Geometric Machine Model for the modelling of sequential, alternative, parallel (synchronous) and nondeterministic computations with stochastic numbers stored in a (possibly infinite) shared memory. The programming language L(D! 1), induced by the Coherence Space of Processes D! 1, can be applied to sequential and parallel products in order to provide recursive definitions for such processes, together with a domain-theoretic semantics of the Stochastic Arithmetic. We analyze both the spacial (ordinal) recursion, related to spacial modelling of the stochastic memory, and the temporal (structural) recursion, given by the inclusion relation modelling partial objects in the ordered structure of process construction.