16 research outputs found
Capturing the Shape of a Point Set with a Line Segment
Get PDFDetecting location-correlated groups in point sets is an important task in a wide variety of applications areas. In addition to merely detecting such groups, the group’s shape carries meaning as well. In this paper, we represent a group’s shape using a simple geometric object, a line segment. Specifically, given a radius r, we say a line segment is representative of a point set P of n points if it is within distance r of each point p ∈ P. We aim to find the shortest such line segment. This problem is equivalent to stabbing a set of circles of radius r using the shortest line segment. We describe an algorithm to find the shortest representative segment in O(n log h + h log³h) time, where h is the size of the convex hull of P. Additionally, we show how to maintain a stable approximation of the shortest representative segment when the points in P move
Density approximation for moving groups
Get PDFSets of moving entities can form groups which travel together for significant amounts of time. Tracking such groups is an important analysis task in a variety of areas, such as wildlife ecology, urban transport, or sports analysis. Correspondingly, recent years have seen a multitude of algorithms to identify and track meaningful groups in sets of moving entities. However, not only the mere existence of one or more groups is an important fact to discover; in many application areas the actual shape of the group carries meaning as well. In this paper we initiate the algorithmic study of the shape of a moving 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 which give a meaningful first idea of the time-varying shape of the group. By combining several approximation techniques, we obtain a kinetic data structure that can approximately track persistent maxima efficiently
Quantifying the spatial scales of animal clusters using density surfaces
No full textAnimal clustering takes place at a variety of spatial scales. While methods to quantify clustering already exist, many of these methods are either scale independent, not parameter-free, or model proximity as a binary function, which makes them unsuitable for anisotropic systems and is not representative of the perception neighbourhood of animals. We describe a method to quantify the degree of clustering of point-location data at different spatial scales, which uses kernel density estimation to construct a density function from the underlying point-location data. We build upon this method to automatically detect cluster diameters using smoothing kernels that better represent the perception neighbourhood of animals. Finally, we test our methods on artificial datasets with varying clustering characteristics, as well as on a dataset of African bush elephants. Our method correctly assigns higher clustering values to spatial scales with high degrees of clustering and accurately outputs a set of spatial scales that correspond to cluster diameters. The accuracy of our method is insensitive to the chosen kernel function. Combined with the parameter-free nature of our method, this allows for easy detection of clustering scales in anisotropic and hierarchically clustered systems, such as animal groups
Kinetic Group Density in 1D
No full textWe are interested in tracking the overall structure of a single group of entities (e.g., people, wildlife, or vehicles) over time. As a first step, we investigate how to characterize and kinetically maintain the density of a one-dimensional group, represented by a point set P of size n. We achieve this with a kinetic data structure that maintains the critical points of an estimate of the density function of P, which is obtained using kernel density estimation. Our KDS is local, compact, responsive, and weakly efficient. However, the total number of events can be Θ(n^2). Therefore, we also show how to maintain an ɛ-approximation of the critical points using a coreset of the trajectories of the points in P. The coreset has size O(1/ɛ^2 log(1/ɛ)), for ɛ > 0, and approximates the critical points well in a topological sense
Density Approximation for Moving Groups
Get PDFSets of moving entities can form groups which travel together for significant amounts of time. Tracking such groups is an important analysis task in a variety of areas, such as wildlife ecology, urban transport, or sports analysis. Correspondingly, recent years have seen a multitude of algorithms to identify and track meaningful groups in sets of moving entities. However, not only the mere existence of one or more groups is an important fact to discover; in many application areas the actual shape of the group carries meaning as well. In this paper we initiate the algorithmic study of the shape of a moving 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 which give a meaningful first idea of the time-varying shape of the group. By combining several approximation techniques, we obtain a kinetic data structure that can approximately track persistent maxima efficiently.</p
Kinetic Group Density in 1D
Get PDFWe are interested in tracking the overall structure of a single group of entities (e.g., people, wildlife, or vehicles) over time. As a first step, we investigate how to characterize and kinetically maintain the density of a one-dimensional group, represented by a point set P of size n. We achieve this with a kinetic data structure that maintains the critical points of an estimate of the density function of P, which is obtained using kernel density estimation. Our KDS is local, compact, responsive, and weakly efficient. However, the total number of events can be Θ(n^2). Therefore, we also show how to maintain an ɛ-approximation of the critical points using a coreset of the trajectories of the points in P. The coreset has size O(1/ɛ^2 log(1/ɛ)), for ɛ > 0, and approximates the critical points well in a topological sense
