Search

We present several results about Delaunay triangulations (DTs) and convex hulls in transdichotomous and hereditary settings: (i) the DT of a planar point set can be computed in expected time O(sort(n)) on a word RAM, where sort(n) is the time to sort n numbers. We assume that the word RAM supports the shuffle operation in constant time; (ii) if we know the ordering of a planar point set in x- and in y-direction, its DT can be found by a randomized algebraic computation tree of expected linear depth; (iii) given a universe U of points in the plane, we construct a data structure D for Delaunay queries: for any P ⊆ U, D can find the DT of P in expected time O(∣P∣ log log ∣U∣); (iv) given a universe U of points in 3-space in general convex position, there is a data structure D for convex hull queries: for any P ⊆ U, D can find the convex hull of P in expected time O(∣P∣(log log ∣U∣)²); (v) given a convex polytope in 3-space with n vertices which are colored with χ ≥ 2 colors, we can split it into the convex hulls of the individual color classes in expected time O(n(log log n)²). [ABSTRACT FROM AUTHOR]

Abstract The Fréchet distance is a metric to compare two curves, which is based on monotone matchings between these curves. We call a matching that results in the Fréchet distance a Fréchet matching. There are often many different Fréchet matchings and not all of these capture the similarity between the curves well. We propose to restrict the set of Fréchet matchings to "natural" matchings and to this end introduce locally correct Fréchet matchings. We prove that at least one such matching exists for two polygonal curves and give an O (N 3 log ⁡ N) algorithm to compute it, where N is the number of edges in both curves. We also present an O (N 2) algorithm to compute a locally correct discrete Fréchet matching. [ABSTRACT FROM AUTHOR]

We present efficient algorithms for segmenting and classifying trajectories based on a movement model parameterised by a single parameter, like the Brownian bridge movement model. Segmentation is the problem of subdividing a trajectory into interior-disjoint parts such that each part is homogeneous in its movement characteristics. We formalise this using the likelihood of the model parameter, and propose a new algorithm for trajectory segmentation based on this. We consider the case where a discrete set of m parameter values is given and present an algorithm to compute an optimal segmentation with respect to an information criterion in O(nm) time for a trajectory with n sampling points. We also present an algorithm that efficiently computes the optimal segmentation if we allow the parameter values to be drawn from a continuous domain. Classification is the problem of assigning trajectories to classes of similar movement characteristics. The set of trajectories might for instance be the subtrajectories resulting from segmenting a trajectory, thus identifying movement phases. We give an algorithm to compute the optimal classification with respect to an information criterion in O(m2+kmlogm) time for m parameter values and k trajectories, assuming bitonic likelihood functions. We also show that classification is NP-hard if the parameter values are allowed to vary continuously and present an algorithm that solves the problem in polynomial time under mild assumptions on the input. [ABSTRACT FROM AUTHOR]

All known algorithms for the Fréchet distance between curves proceed in two steps: first, they construct an efficient oracle for the decision version; second, they use this oracle to find the optimum from a finite set of critical values. We present a novel approach that avoids the detour through the decision version. This gives the first quadratic time algorithm for the Fréchet distance between polygonal curves in $$\mathbb {R}^d$$ under polyhedral distance functions (e.g., $$L_1$$ and $$L_\infty $$ ). We also get a $$(1+\varepsilon )$$ -approximation of the Fréchet distance under the Euclidean metric, in quadratic time for any fixed $$\varepsilon > 0$$ . For the exact Euclidean case, our framework currently yields an algorithm with running time $$O(n^2 \log ^2 n)$$ . However, we conjecture that it may eventually lead to a faster exact algorithm. [ABSTRACT FROM AUTHOR]

An important but strongly NP-hard problem in automated cartography is how to best place textual labels for point features on a static map. We examine the complexity of various generalizations of this problem for dynamic and/or interactive maps. Specifically, we show that it is strongly PSPACE-complete to decide whether there is a smooth dynamic labeling (function from time to static labelings) when the points move, when points are added and removed, or when the user pans, rotates, and/or zooms their view of the points. In doing so we develop a framework from which a wide variety of labeling hardness results can be obtained, including (next to the PSPACE-hardness results) both known and new results on the NP-hardness of static labeling. [ABSTRACT FROM AUTHOR]

A constant-work-space algorithm has read-only access to an input array and may use only O ( 1 ) additional words of O ( log n ) bits, where n is the input size. We show how to triangulate a plane straight-line graph with n vertices in O ( n 2 ) time and constant work-space. We also consider the problem of preprocessing a simple polygon P for shortest path queries, where P is given by the ordered sequence of its n vertices. For this, we relax the space constraint to allow s words of work-space. After quadratic preprocessing, the shortest path between any two points inside P can be found in O ( n 2 / s ) time. [ABSTRACT FROM AUTHOR]

Abstract: A constant-work-space algorithm has read-only access to an input array and may use only additional words of bits, where n is the input size. We show how to triangulate a plane straight-line graph with n vertices in time and constant work-space. We also consider the problem of preprocessing a simple polygon P for shortest path queries, where P is given by the ordered sequence of its n vertices. For this, we relax the space constraint to allow s words of work-space. After quadratic preprocessing, the shortest path between any two points inside P can be found in time. [Copyright &y& Elsevier]

We investigate the concept of a median among a set of trajectories. We establish criteria that a 'median trajectory' should meet, and present two different methods to construct a median for a set of input trajectories. The first method is very simple, while the second method is more complicated and uses homotopy with respect to sufficiently large faces in the arrangement formed by the trajectories. We give algorithms for both methods, analyze the worst-case running time, and show that under certain assumptions both methods can be implemented efficiently. We empirically compare the output of both methods on randomly generated trajectories, and evaluate whether the two methods yield medians that are according to our intuition. Our results suggest that the second method, using homotopy, performs considerably better. [ABSTRACT FROM AUTHOR]

Spatially aggregated data is frequently used in geographical applications. Often spatial data analysis on aggregated data is performed in the same way as on exact data, which ignores the fact that we do not know the actual locations of the data. We here propose models and methods to take aggregation into account. For this we focus on the problem of locating clusters in aggregated data. More specifically, we study the problem of locating clusters in spatially aggregated health data. The data is given as a subdivision into regions with two values per region, the number of cases and the size of the population at risk. We formulate the problem as finding a placement of a cluster window of a given shape such that a cluster function depending on the population at risk and the cases is maximized. We propose area-based models to calculate the cases (and the population at risk) within a cluster window. These models are based on the areas of intersection of the cluster window with the regions of the subdivision. We show how to compute a subdivision such that within each cell of the subdivision the areas of intersection are simple functions. We evaluate experimentally how taking aggregation into account influences the location of the clusters found. [ABSTRACT FROM AUTHOR]

Abstract: A natural time-dependent similarity measure for two trajectories is their average distance at corresponding times. We give algorithms for computing the most similar subtrajectories under this measure, assuming the two trajectories are given as two polygonal, possibly self-intersecting lines with time stamps. For the case when a minimum duration of the subtrajectories is specified and the subtrajectories must start at corresponding times, we give a linear-time algorithm. The algorithm is based on a result of independent interest: We present a linear-time algorithm to find, for a piece-wise monotone function, an interval of at least a given length that has minimum average value. In the case that the subtrajectories may start at non-corresponding times, it appears difficult to give exact algorithms, even if the duration of the subtrajectories is fixed. For this case, we give -approximation algorithms, for both fixed duration and when only a minimum duration is specified. [Copyright &y& Elsevier]

In this paper we consider the problem of detecting commuting patterns in a trajectory. For this we search for similar subtrajectories. To measure spatial similarity we choose the Fréchet distance and the discrete Fréchet distance between subtrajectories, which are invariant under differences in speed. We give several approximation algorithms, and also show that the problem of finding the 'longest' subtrajectory cluster is as hard as MaxClique to compute and approximate. [ABSTRACT FROM AUTHOR]

Time plays an important role in the analysis of moving object data. For many applications it is not sufficient to only compare objects at exactly the same times, or to consider only the geometry of their trajectories. We show how to leverage between these two approaches by extending a tool from curve analysis, namely the free space diagram. Our approach also allows us to take further attributes of the objects like speed or direction into account. We demonstrate the usefulness of the new tool by applying it to the problem of detecting single file movement. A single file is a set of moving entities, which are following each other, one behind the other. Our algorithm is the first one developed for detecting such movement patterns. For this application, we analyse demonstrate the performance of our tool both theoretically experimentally. [ABSTRACT FROM AUTHOR]

Abstract: The flow complex is a geometric structure, similar to the Delaunay tessellation, to organize a set of (weighted) points in . Flow shapes are topological spaces corresponding to substructures of the flow complex. The flow complex and flow shapes have found applications in surface reconstruction, shape matching, and molecular modeling. In this article we give an algorithm for computing the flow complex of weighted points in any dimension. The algorithm reflects the recursive structure of the flow complex. On the basis of the algorithm we establish a topological similarity between flow shapes and the nerve of a corresponding ball set, namely homotopy equivalence. [Copyright &y& Elsevier]