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.

Condensation versus air density change as a major cause of airflow: experimental evidence, link to data files and videos

The dominant model of atmospheric circulation posits that hot air rises, creating horizontal winds. A second major driver has recently been proposed by Makarieva and Gorshkov in their biotic pump theory (BPT), which suggests that evapotranspiration from natural closed-canopy forests causes intense condensation, and hence winds from ocean to land. Critics of the BPT argue that air movement to fill the partial vacuum caused by condensation is always isotropic, and therefore causes no net air movement (Bunyard, 2015, hdl:11232/397). This paper explores the physics of water condensation under mild atmospheric conditions, within a purpose-designed square-section 4.8 m-tall closed-system structure. Two enclosed vertical columns are connected at top and bottom by two horizontal tunnels, around which 19.5 m**3 of atmospheric air can circulate freely, allowing rotary airflows in either direction. This air can be cooled and/or warmed by refrigeration pipes and a heating mat, and changes in airflow, temperature, humidity and barometric pressure measured in real time. The study investigates whether the "hot-air-rises" or an implosive condensation model can better explain the results of more than 100 experiments. The data show a highly significant correlation (R2 >0.96, p value <0.001) between observed airflows and partial pressure changes from condensation. While the kinetic energy of the refrigerated air falls short of that required in bringing about observed airflows by a factor of at least 30, less than a tenth of the potential kinetic energy from condensation is shown to be sufficient. The assumption that condensation of water vapour is always isotropic is therefore incorrect. Condensation can be anisotropic, and in the laboratory does cause sustained airflow.