Geometric Algorithms for Wildlife Ecology

Wildlife protection has become an increasingly important task in recent years. Locating wildlife animals and analyzing their movement behavior can offer valuable support to these protection efforts. Advances in tracking technology—such as the use of drones—have made it possible to collect large volumes of movement data from herds of animals. This development naturally creates a need for efficient algorithms to process and analyze such data, ultimately enabling the extraction of meaningful patterns. These patterns can then be related to behavioral states, or be used to predict environmental factors causing this behavior. In this thesis, we present geometric tools for analyzing salient patterns in the collective movement behavior of animal groups, as well as efficient algorithms to locate these animals. We initiate the algorithmic study of moving groups by identifying and tracking particularly dense areas. These dense areas provide a meaningful first idea of the time-varying shape of the group. We use kernel density estimation to model the density within a group and show how to efficiently maintain an approximation of this density description over time. Furthermore, we track persistent maxima in the density function as the group moves. By combining several approximation techniques, we obtain a kinetic data structure that can track the approximate location of these persistent maxima efficiently. Computing a density function using kernel density estimation requires a suitable scale parameter for effective analysis. As such, we next describe a method to derive this scale parameter directly from the data. Our method first quantifies the degree of clustering in the data over all spatial scales, then automatically detects salient scale levels. We test our method on a number of synthetic data sets, and on an actual data set of African bush elephants. These tests show that our method accurately obtains the scale levels at which the data shows locally maximal clustering behavior, without requiring user-specified input parameters. Next, we study the shape of location-correlated groups more directly. We represent a group's shape using a simple geometric object, a line segment, and aim to find the shortest line segment that represents the shape of the group well. Here, we define a line segment to be representative when it is within a given distance threshold of all entities in the group. We describe an algorithm to find the shortest representative segment, which bears similarities to the popular rotating calipers algorithm. Additionally, we show how to maintain a stable approximation of this representative segment when the group moves. Lastly, we study a theoretical version of the problem of collecting animal location data using a drone. We model this as a variant of the searching problem where the environment consists of a known terrain and the goal is to obtain visibility of an unknown target point on the surface of the terrain. The goal is to devise a searching strategy that minimizes the worst-case ratio between the distance traveled by the searching strategy and the minimum travel distance needed to detect the target. For 1.5D terrains we present a nearly-optimal searching strategy, which extends directly to the case where the searcher has no knowledge of the terrain beforehand. For 2.5D terrains we show that the optimal searching strategy depends on the maximum slope of the terrain and is hence unbounded in general. We complement the lower bound with a searching strategy based on the maximum slope of the known terrain.