1. 
 Andersson, Mattias, et al.
(författare)

Approximate distance oracles for graphs with dense clusters
 2007

Ingår i: Computational Geometry.  Elsevier B.V.. ; 37:3, s. 142154

Tidskriftsartikel (refereegranskat)abstract
 Let H1=(V,E1) be a collection of N pairwise vertex disjoint O(1)spanners where the weight of an edge is equal to the Euclidean distance between its endpoints. Let H2=(V,E2) be the graph on V with M edges of nonnegative weight. The union of the two graphs is denoted G=(V,E1 u E2). We present a data structure of size O(M^2 + nlogn) that answers (1+ε)approximate shortest path queries in G in constant time, where ε>0 is constant.


2. 
 Andersson, Mattias, et al.
(författare)

Reporting leaders and followers among trajectories of moving point objects
 2008

Ingår i: GEOINFORMATICA.  SPRINGER.  13846175. ; 12:4, s. 497528

Tidskriftsartikel (refereegranskat)abstract
 Widespread availability of location aware devices (such as GPS receivers) promotes capture of detailed movement trajectories of people, animals, vehicles and other moving objects, opening new options for a better understanding of the processes involved. In this paper we investigate spatiotemporal movement patterns in large tracking data sets. We present a natural definition of the pattern 'one object is leading others', which is based on behavioural patterns discussed in the behavioural ecology literature. Such leadership patterns can be characterised by a minimum time length for which they have to exist and by a minimum number of entities involved in the pattern. Furthermore, we distinguish two models (discrete and continuous) of the time axis for which patterns can start and end. For all variants of these leadership patterns, we describe algorithms for their detection, given the trajectories of a group of moving entities. A theoretical analysis as well as experiments show that these algorithms efficiently report leadership patterns.


3. 
 Andersson, Mattias, et al.
(författare)

Reporting leadership patterns among trajectories
 2007

Ingår i: Proceedings of the 2007 ACM symposium on Applied computing.  ACM Press.  1595934804 ; s. 37

Konferensbidrag (refereegranskat)abstract
 Widespread availability of location aware devices (such as GPS receivers) promotes capture of detailed movement trajectories of people, animals, vehicles and other moving objects, opening new options for a better understanding of the processes involved. In this paper we investigate spatiotemporal movement patterns in large tracking data sets. We present a natural definition of the pattern 'one object is leading others', and discuss how such leadership patterns can be computed from a group of moving entities. The proposed definition is based on behavioural patterns discussed in the behavioural ecology literature. We also present several algorithms for computing the pattern, and they are analysed both theoretically and experimentally.


4. 
 Andersson, Mattias, et al.
(författare)

Restricted mesh simplification using edge contractions
 2006

Ingår i: Computing and combinatorics / Lecture notes in computer science.  Springer.  03029743.  9783540369257 ; 4112, s. 196204

Konferensbidrag (refereegranskat)abstract
 We consider the problem of simplifying a triangle mesh using edge contractions, under the restriction that the resulting vertices must be a subset of the input set. That is, contraction of an edge must be made onto one of its adjacent vertices. In order to maintain a high number of contractible edges under this restriction, a small modification of the mesh around the edge to be contracted is allowed. Such a contraction is denoted a 2step contraction. Given m "important" points or edges it is shown that a simplification hierarchy of size O(n) and depth O(log(n/m)) may be constructed in O(n) time. Further, for many edges not even 2step contractions may be enough, and thus, the concept is generalized to kstep contractions.


5. 
 Andersson, Mattias, et al.
(författare)

Restricted mesh simplification using edge contractions
 2009

Ingår i: International Journal of Computational Geometry & Applications.  World Scientific Publishing Company.  02181959. ; 19:3, s. 247265

Tidskriftsartikel (refereegranskat)abstract
 We consider the problem of simplifying a planar triangle mesh using edge contractions, under the restriction that the resulting vertices must be a subset of the input set. That is, contraction of an edge must be made on to one of its adjacent vertices, which results in removing the other adjacent vertex. We show that if the perimeter of the mesh consists of at most five vertices, then we can always find a vertex not on the perimeter which can be removed in this way. If the perimeter consists of more than five vertices such a vertex may not exist. In order to maintain a higher number of removable vertices under the above restriction, we study edge flips which can be performed in a visually smooth way. A removal of a vertex which is preceded by one such smooth operation is called a 2step removal. Moreover, we introduce the possibility that the user defines "important" vertices (or edges) which have to remain intact. Given m such important vertices, or edges, we show that a simplification hierarchy of size O(n) and depth O(log(n/m))can be constructed by 2step removals in O(n) time, such that the simplified graph contains the m important vertices and edges, and at most O(m) other vertices from the input graph. In some triangulations, many vertices may not even be 2step removable. In order to provide the option to remove such vertices, we also define and examine kstep removals. This increases the lower bound on the number of removable vertices.

