ORCID Profile
0000-0002-6778-7990
Current Organisation
University of Sydney
Does something not look right? The information on this page has been harvested from data sources that may not be up to date. We continue to work with information providers to improve coverage and quality. To report an issue, use the Feedback Form.
Research Topics
In Research Link Australia (RLA), "Research Topics" refer to ANZSRC FOR and SEO codes. These topics are either sourced from ANZSRC FOR and SEO codes listed in researchers' related grants or generated by a large language model (LLM) based on their publications.
Top 5 Research Topics
ANZSRC Field of Research (FoR)
Analysis of Algorithms and Complexity | Computation Theory and Mathematics | Computation Theory and Mathematics not elsewhere classified | Pattern Recognition and Data Mining | Data Structures
ANZSRC Socio-Economic Objective (SEO)
Expanding Knowledge in the Information and Computing Sciences | Emerging Defence Technologies | Road Public Transport | Expanding Knowledge in the Mathematical Sciences |
Related Links
Publications
A GPU approach to subtrajectory clustering using the Fréchet distance
Publisher: ACM
Date: 06-11-2012
Detecting Commuting Patterns by Clustering Subtrajectories
Publisher: Springer Berlin Heidelberg
Date: 2008
Fast Fréchet Distance Between Curves with Long Edges
Publisher: World Scientific Pub Co Pte Lt
Date: 06-2019
DOI: 10.1142/S0218195919500043
Abstract: Computing the Fréchet distance between two polygonal curves takes roughly quadratic time. In this paper, we show that for a special class of curves the Fréchet distance computations become easier. Let [Formula: see text] and [Formula: see text] be two polygonal curves in [Formula: see text] with [Formula: see text] and [Formula: see text] vertices, respectively. We prove four results for the case when all edges of both curves are long compared to the Fréchet distance between them: (1) a linear-time algorithm for deciding the Fréchet distance between two curves, (2) an algorithm that computes the Fréchet distance in [Formula: see text] time, (3) a linear-time [Formula: see text]-approximation algorithm, and (4) a data structure that supports [Formula: see text]-time decision queries, where [Formula: see text] is the number of vertices of the query curve and [Formula: see text] the number of vertices of the preprocessed curve.
Range-efficient consistent sampling and locality-sensitive hashing for polygons
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
Date: 2017
Approximating the packedness of polygonal curves
Publisher: Elsevier BV
Date: 2023
Quickest paths in anisotropic media
Publisher: Springer Berlin Heidelberg
Date: 2011
Local Routing in a Tree Metric 1-Spanner
Publisher: Springer International Publishing
Date: 2020
Spatio-Temporal Analysis of Team Sports
Publisher: Association for Computing Machinery (ACM)
Date: 11-04-2017
DOI: 10.1145/3054132
Abstract: Team-based invasion sports such as football, basketball, and hockey are similar in the sense that the players are able to move freely around the playing area and that player and team performance cannot be fully analysed without considering the movements and interactions of all players as a group. State-of-the-art object tracking systems now produce spatio-temporal traces of player trajectories with high definition and high frequency, and this, in turn, has facilitated a variety of research efforts, across many disciplines, to extract insight from the trajectories. We survey recent research efforts that use spatio-temporal data from team sports as input and involve non-trivial computation. This article categorises the research efforts in a coherent framework and identifies a number of open research questions.
Sparse geometric graphs with small dilation
Publisher: Springer Berlin Heidelberg
Date: 2005
DOI: 10.1007/11602613_7
Geometric spanners for weighted point sets
Publisher: Springer Berlin Heidelberg
Date: 2009
Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams
Publisher: Springer Berlin Heidelberg
Date: 2006
DOI: 10.1007/11682462_12
A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM
Publisher: World Scientific Pub Co Pte Lt
Date: 06-2009
DOI: 10.1142/S0218195909002952
Abstract: We consider the following packing problem. Let α be a fixed real in (0, 1]. We are given a bounding rectangle ρ and a set [Formula: see text] of n possibly intersecting unit disks whose centers lie in ρ. The task is to pack a set [Formula: see text] of m disjoint disks of radius α into ρ such that no disk in B intersects a disk in [Formula: see text], where m is the maximum number of unit disks that can be packed. In this paper we present a polynomial-time algorithm for α = 2/3. So far only the case of packing squares has been considered. For that case, Baur and Fekete have given a polynomial-time algorithm for α = 2/3 and have shown that the problem cannot be solved in polynomial time for any α 13/14 unless [Formula: see text].
Region-restricted clustering for geographic data mining
Publisher: Elsevier BV
Date: 04-2009
Computing longest duration flocks in trajectory data
Publisher: ACM
Date: 10-11-2006
Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies
Publisher: Elsevier BV
Date: 09-2010
Barrier coverage with non-uniform lengths to minimize aggregate movements
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
Date: 2017
Constrained higher order Delaunay triangulations
Publisher: Elsevier BV
Date: 03-2005
Faster algorithms for computing plurality points
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
Date: 2016
Fréchet queries in geometric trees
Publisher: Springer Berlin Heidelberg
Date: 2013
On Practical Nearest Sub-Trajectory Queries under the Fréchet Distance
Publisher: Association for Computing Machinery (ACM)
Date: 02-05-2023
DOI: 10.1145/3587426
Abstract: We study the problem of sub-trajectory nearest-neighbor queries on polygonal curves under the continuous Fréchet distance. Given an n vertex trajectory P and an m vertex query trajectory Q , we seek to report a vertex-aligned sub-trajectory P ′ of P that is closest to Q , i.e., P′ must start and end on contiguous vertices of P . Since in real data P typically contains a very large number of vertices, we focus on answering queries, without restrictions on P or Q , using only precomputed structures of 𝒪(n) size. We use three baseline algorithms from straightforward extensions of known work however, they have impractical performance on realistic inputs. Therefore, we propose a new Hierarchical Simplification Tree (HST) data structure and an adaptive clustering-based query algorithm that efficiently explores relevant parts of P . The core of our query methods is a novel greedy-backtracking algorithm that solves the Fréchet decision problem using 𝒪(n+m) space and 𝒪O(nm) time in the worst case. Experiments on real and synthetic data show that our heuristic effectively prunes the search space and greatly reduces computations compared to baseline approaches.
Analyzing delays in trajectories
Publisher: IEEE
Date: 04-2015
Algorithms for hotspot computation on trajectory data
Publisher: ACM
Date: 05-11-2013
Approximating minimum manhattan networks: (Extended abstract)
Publisher: Springer Berlin Heidelberg
Date: 1999
Detecting areas visited regularly
Publisher: Springer Berlin Heidelberg
Date: 2010
I/O-efficiently pruning dense spanners
Publisher: Springer Berlin Heidelberg
Date: 2005
DOI: 10.1007/11589440_11
Turbocharging Treewidth Heuristics
Publisher: Springer Science and Business Media LLC
Date: 17-08-2018
Fast query structures in anisotropic media
Publisher: Elsevier BV
Date: 07-2013
A simple and efficient kinetic spanner
Publisher: Elsevier BV
Date: 04-2010
Editorial, SEA 2014 special issue
Publisher: Association for Computing Machinery (ACM)
Date: 05-04-2016
DOI: 10.1145/2854021
Restricted mesh simplification using edge contractions
Publisher: World Scientific Pub Co Pte Lt
Date: 06-2009
DOI: 10.1142/S0218195909002940
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 onto 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 2-step 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 2-step 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 2-step removable. In order to provide the option to remove such vertices, we also define and examine k-step removals. This increases the lower bound on the number of removable vertices.
On spanners of geometric graphs
Publisher: Springer Berlin Heidelberg
Date: 2006
DOI: 10.1007/11785293_36
Barrier coverage with uniform radii in 2D
Publisher: Springer International Publishing
Date: 2017
Approximate one-to-one point pattern matching
Publisher: Elsevier BV
Date: 08-2012
International Journal of Foundations of Computer Science: Preface
Publisher: World Scientific Pub Co Pte Lt
Date: 02-2009
Translation Invariant Fréchet Distance Queries
Publisher: Springer Science and Business Media LLC
Date: 14-08-2021
A simple and efficient kinetic spanner
Publisher: ACM
Date: 09-06-2008
A fast approximation algorithm for TSP with neighborhoods and red-blue separation
Publisher: Springer Berlin Heidelberg
Date: 1999
Of motifs and goals: Mining trajectory data
Publisher: ACM
Date: 06-11-2012
Distance-preserving approximations of polygonal paths
Publisher: Elsevier BV
Date: 04-2007
Fast algorithms for diameter-optimally augmenting paths
Publisher: Springer Berlin Heidelberg
Date: 2015
Detecting regular visit patterns
Publisher: Springer Science and Business Media LLC
Date: 21-11-2011
Minimum weight pseudo-triangulations
Publisher: Elsevier BV
Date: 10-2007
Faster Algorithms for Computing Plurality Points
Publisher: Association for Computing Machinery (ACM)
Date: 16-06-2018
DOI: 10.1145/3186990
Abstract: Let V be a set of n points in R d , which we call voters. A point p ∈ R d is preferred over another point p ′ ∈ R d by a voter υ ∈ V if dist(υ, p ) dist(υ, p ′). A point p is called a plurality point if it is preferred by at least as many voters as any other point p ′. We present an algorithm that decides in O ( n log n ) time whether V admits a plurality point in the L 2 norm and, if so, finds the (unique) plurality point. We also give efficient algorithms to compute a minimum-cost subset W ⊂ V such that V \ W admits a plurality point, and to compute a so-called minimum-radius plurality ball. Finally, we consider the problem in the personalized L 1 norm, where each point υ ∈ V has a preference vector 〈 w 1 (υ),…, w d (υ)〉 and the distance from υ to any point p ∈ R d is given by ∑ i =1 d w i (υ)· | x i (υ)− x i ( p )|. For this case we can compute in O ( n d −1 ) time the set of all plurality points of V . When all preference vectors are equal, the running time improves to O ( n ).
Box-trees and R-trees with near-optimal query time
Publisher: Springer Science and Business Media LLC
Date: 08-2002
Computational Movement Analysis
Publisher: Springer Berlin Heidelberg
Date: 2011
On spanners of geometric graphs
Publisher: World Scientific Pub Co Pte Lt
Date: 02-2009
DOI: 10.1142/S0129054109006486
Abstract: Given a connected geometric graph G, we consider the problem of constructing a t-spanner of G having the minimum number of edges. We prove that for every real number t with [Formula: see text], there exists a connected geometric graph G with n vertices, such that every t-spanner of G contains Ω(n 1+1/t ) edges. This bound almost matches the known upper bound, which states that every connected weighted graph with n vertices contains a t-spanner with O(n 1+2/(t-1) ) edges. We also prove that the problem of deciding whether a given geometric graph contains a t-spanner with at most K edges is NP-hard. Previously, this NP-hardness result was only known for non-geometric graphs.
Editorial, SWAT 2008 special issue
Publisher: Springer Science and Business Media LLC
Date: 20-05-2010
Higher order Delaunay triangulations
Publisher: Elsevier BV
Date: 07-2002
Compact Flow Diagrams for State Sequences
Publisher: Springer International Publishing
Date: 2016
Fast algorithms for approximate Fréchet matching queries in geometric trees
Publisher: Elsevier BV
Date: 08-2015
Sparse geometric graphs with small dilation
Publisher: Elsevier BV
Date: 08-2008
Football analysis using spatio-temporal tools
Publisher: Elsevier BV
Date: 09-2014
Shortcuts for the circle
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
Date: 2017
Geometric spanners for weighted point sets
Publisher: Springer Science and Business Media LLC
Date: 04-11-2011
Finding popular places
Publisher: World Scientific Pub Co Pte Lt
Date: 02-2010
DOI: 10.1142/S0218195910003189
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. We investigate spatio-temporal movement patterns in large tracking data sets, i.e. in large sets of polygonal paths. Specifically, we study so-called 'popular places', that is, regions that are visited by many entities. Given a set of polygonal paths with a total of [Formula: see text] vertices, we look at the problem of computing such popular places in two different settings. For the discrete model, where only the vertices of the polygonal paths are considered, we propose an [Formula: see text] algorithm and for the continuous model, where also the straight line segments between the vertices of a polygonal path are considered, we develop an [Formula: see text] algorithm. We also present lower bounds and hardness results.
Facility location and the geometric minimum-diameter spanning tree
Publisher: Elsevier BV
Date: 2004
A GPU approach to subtrajectory clustering using the Fréchet distance
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date: 04-2015
On the expected maximum degree of Gabriel and Yao graphs
Publisher: Cambridge University Press (CUP)
Date: 12-2009
Abstract: Motivated by applications of Gabriel graphs and Yao graphs in wireless ad-hoc networks, we show that the maximum degree of a random Gabriel graph or Yao graph defined on n points drawn uniformly at random from a unit square grows as Θ (log n / log log n ) in probability.
Farthest-polygon Voronoi diagrams
Publisher: Elsevier BV
Date: 05-2011
Special issue selected papers from CATS 2006: Preface
Publisher: World Scientific Pub Co Pte Lt
Date: 04-2007
Approximate distance oracles revisited
Publisher: Springer Berlin Heidelberg
Date: 2002
Reporting leadership patterns among trajectories
Publisher: ACM
Date: 11-03-2007
Balanced partition of minimum spanning trees
Publisher: World Scientific Pub Co Pte Lt
Date: 08-2003
DOI: 10.1142/S0218195903001190
Abstract: To better handle situations where additional resources are available to carry out a task, many problems from the manufacturing industry involve iding a task into a number of smaller tasks, while optimizing a specific objective function. In this paper we consider the problem of partitioning a given set [Formula: see text] of n points in the plane into k subsets, [Formula: see text], such that [Formula: see text] is minimized. Variants of this problem arise in applications from the shipbuilding industry. We show that this problem is NP-hard, and we also present an approximation algorithm for the problem, in the case when k is a fixed constant. The approximation algorithm runs in time O(n log n) and produces a partition that is within a factor (4/3+ε) of the optimal if k=2, and a factor (2+ε) otherwise.
Dimensionality reduction for long duration and complex spatio-temporal queries
Publisher: ACM
Date: 11-03-2007
Area-preserving approximations of polygonal paths
Publisher: Elsevier BV
Date: 12-2006
Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams
Publisher: Springer Science and Business Media LLC
Date: 03-11-2018
Fast greedy algorithms for constructing sparse geometric spanners
Publisher: Society for Industrial & Applied Mathematics (SIAM)
Date: 2002
Turbocharging treewidth heuristics
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
Date: 2017
Algorithms for marketing-mix optimization
Publisher: Springer Science and Business Media LLC
Date: 23-02-2011
Efficient detection of patterns in 2D trajectories of moving points
Publisher: Springer Science and Business Media LLC
Date: 20-01-2007
Improving the stretch factor of a geometric network by edge augmentation
Publisher: Society for Industrial & Applied Mathematics (SIAM)
Date: 2008
DOI: 10.1137/050635675
When is Red-Blue Nonblocker Fixed-Parameter Tractable?
Publisher: Springer International Publishing
Date: 2018
Finding the Most Relevant Fragments in Networks
Publisher: Journal of Graph Algorithms and Applications
Date: 2010
DOI: 10.7155/JGAA.00209
A fast algorithm for data collection along a fixed track
Publisher: Springer Berlin Heidelberg
Date: 2013
Fast fréchet distance between curves with long edges
Publisher: ACM
Date: 12-04-2018
On graphs supporting greedy forwarding for directional wireless networks
Publisher: IEEE
Date: 06-2012
Classification of Passes in Football Matches Using Spatiotemporal Data
Publisher: Association for Computing Machinery (ACM)
Date: 30-06-2017
DOI: 10.1145/3105576
Abstract: A knowledgeable observer of a game of football (soccer) can make a subjective evaluation of the quality of passes made between players during the game, such as rating them as Good , OK , or Bad . In this article, we consider the problem of producing an automated system to make the same evaluation of passes and present a model to solve this problem. Recently, many professional football leagues have installed object tracking systems in their stadiums that generate high-resolution and high-frequency spatiotemporal trajectories of the players and the ball. Beginning with the thesis that much of the information required to make the pass ratings is available in the trajectory signal, we further postulated that using complex data structures derived from computational geometry would enable domain football knowledge to be included in the model by computing metric variables in a principled and efficient manner. We designed a model that computes a vector of predictor variables for each pass made and uses machine learning techniques to determine a classification function that can accurately rate passes based only on the predictor variable vector. Experimental results show that the learned classification functions can rate passes with 90.2% accuracy. The agreement between the classifier ratings and the ratings made by a human observer is comparable to the agreement between the ratings made by human observers, and suggests that significantly higher accuracy is unlikely to be achieved. Furthermore, we show that the predictor variables computed using methods from computational geometry are among the most important to the learned classifiers.
Augmenting Graphs to Minimize the Diameter
Publisher: Springer Science and Business Media LLC
Date: 16-05-2014
TSP with neighborhoods of varying size
Publisher: Elsevier BV
Date: 09-2005
Finding Pairwise Intersections Inside a Query Range
Publisher: Springer Science and Business Media LLC
Date: 31-10-2017
Planar visibility: Testing and counting
Publisher: ACM
Date: 13-06-2010
Quickest path queries on transportation network
Publisher: Elsevier BV
Date: 08-2014
Finding pairwise intersections inside a query range
Publisher: Springer International Publishing
Date: 2015
Approximation algorithms for covering polygons with squares and similar problems
Publisher: Springer Berlin Heidelberg
Date: 1997
The Mutual Visibility Problem for Fat Robots
Publisher: Springer Nature Switzerland
Date: 2023
Augmenting Graphs to Minimize the Diameter
Publisher: Springer Berlin Heidelberg
Date: 2013
Aperture-Angle and Hausdorff-Approximation of Convex Figures
Publisher: Springer Science and Business Media LLC
Date: 10-10-2007
Chips on wafers, or packing rectangles into grids
Publisher: Elsevier BV
Date: 02-2005
Approximate distance oracles for geometric spanners
Publisher: Association for Computing Machinery (ACM)
Date: 03-2008
Abstract: Given an arbitrary real constant ε 0, and a geometric graph G in d -dimensional Euclidean space with n points, O ( n ) edges, and constant dilation, our main result is a data structure that answers (1 + ε)-approximate shortest-path-length queries in constant time. The data structure can be constructed in O ( n log n ) time using O ( n log n ) space. This represents the first data structure that answers (1 + ε)-approximate shortest-path queries in constant time, and hence functions as an approximate distance oracle. The data structure is also applied to several other problems. In particular, we also show that approximate shortest-path queries between vertices in a planar polygonal domain with “rounded” obstacles can be answered in constant time. Other applications include query versions of closest-pair problems, and the efficient computation of the approximate dilations of geometric graphs. Finally, we show how to extend the main result to answer (1 + ε)-approximate shortest-path-length queries in constant time for geometric spanner graphs with m = ω( n ) edges. The resulting data structure can be constructed in O ( m + n log n ) time using O ( n log n ) space.
Increasing-Chord Graphs On Point Sets
Publisher: Journal of Graph Algorithms and Applications
Date: 2015
DOI: 10.7155/JGAA.00348
A Dynamic Data Structure for Approximate Proximity Queries in Trajectory Data
Publisher: ACM
Date: 07-11-2017
Constrained free space diagrams: a tool for trajectory analysis
Publisher: Informa UK Limited
Date: 02-06-2010
Lower bounds for approximate polygon decomposition and minimum gap
Publisher: Elsevier BV
Date: 02-2002
Football analysis using spatio-temporal tools
Publisher: ACM
Date: 06-11-2012
Reporting Leaders and Followers among Trajectories of Moving Point Objects
Publisher: Springer Science and Business Media LLC
Date: 26-10-2007
On R-trees with low query complexity
Publisher: Elsevier BV
Date: 04-2003
Region-fault tolerant geometric spanners
Publisher: Springer Science and Business Media LLC
Date: 30-01-2009
A Generalization of the Convex Kakeya Problem
Publisher: Springer Berlin Heidelberg
Date: 2012
Automated Classification of Passing in Football
Publisher: Springer International Publishing
Date: 2015
A parallel approximation algorithm for minimum weight triangulation (Extended abstract)
Publisher: Springer Berlin Heidelberg
Date: 1998
Handbook of Approximation Algorithms and Metaheuristics
Publisher: Chapman and Hall/CRC
Date: 15-05-2007
Fast Fréchet queries
Publisher: Elsevier BV
Date: 08-2013
Reporting flock patterns
Publisher: Elsevier BV
Date: 11-2008
Fast Fréchet Queries
Publisher: Springer Berlin Heidelberg
Date: 2011
On the number of upward planar orientations of maximal planar graphs
Publisher: Elsevier BV
Date: 08-2014
Detecting single file movement
Publisher: ACM
Date: 05-11-2008
Algorithm Theory - SWAT 2000
Publisher: Springer Berlin Heidelberg
Date: 2000
Close Approximations of Minimum Rectangular Coverings
Publisher: Springer Science and Business Media LLC
Date: 1999
Editorial: COCOON 2012 special issue
Publisher: Springer Science and Business Media LLC
Date: 13-06-2014
Box-trees for collision checking in industrial installations
Publisher: Elsevier BV
Date: 06-2004
Aperture-angle and Hausdorff-approximation of convex figures
Publisher: ACM Press
Date: 2007
Compact Flow Diagrams for State Sequences
Publisher: Association for Computing Machinery (ACM)
Date: 04-12-2017
DOI: 10.1145/3150525
Abstract: We introduce the concept of using a flow diagram to compactly represent the segmentation of a large number of state sequences according to a set of criteria. We argue that this flow diagram representation gives an intuitive summary that allows the user to detect patterns within the segmentations. In essence, our aim is to generate a flow diagram with a minimum number of nodes that models a segmentation of the states in the input sequences. For a small number of state sequences we present efficient algorithms to compute a minimal flow diagram. For a large number of state sequences, we show that it is unlikely that efficient algorithms exist. Specifically, the problem is W [1]-hard if the number of state sequences is taken as a parameter. We introduce several heuristics for this problem. We argue about the usefulness of the flow diagram by applying the algorithms to two problems in sports analysis, and evaluate the performance of our algorithms on a football dataset and synthetic data.
SEFE with No Mapping via Large Induced Outerplane Graphs in Plane Graphs
Publisher: Springer Berlin Heidelberg
Date: 2013
A fast algorithm for data collection along a fixed track
Publisher: Elsevier BV
Date: 10-2014
Finding the best shortcut in a geometric network
Publisher: ACM
Date: 06-06-2005
DETECTING COMMUTING PATTERNS BY CLUSTERING SUBTRAJECTORIES
Publisher: World Scientific Pub Co Pte Ltd
Date: 06-2011
DOI: 10.1142/S0218195911003652
Abstract: 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.
Approximate distance oracles for graphs with dense clusters
Publisher: Elsevier BV
Date: 08-2007
Ordered theta graphs
Publisher: Elsevier BV
Date: 05-2004
A Generalization of the Convex Kakeya Problem
Publisher: Springer Science and Business Media LLC
Date: 19-09-2013
A visual analysis of changes to weighted self-organizing map patterns
Publisher: Springer International Publishing
Date: 2017
Measuring the similarity of geometric graphs
Publisher: Springer Berlin Heidelberg
Date: 2009
Constructing minimum-interference networks
Publisher: Elsevier BV
Date: 08-2008
A linear-time heuristic for minimum rectangular coverings
Publisher: Springer Berlin Heidelberg
Date: 1997
DOI: 10.1007/BFB0036193
Constructing plane spanners of bounded degree and low weight
Publisher: Springer Science and Business Media LLC
Date: 20-05-2005
SEFE without Mapping via Large Induced Outerplane Graphs in Plane Graphs
Publisher: Wiley
Date: 30-04-2015
DOI: 10.1002/JGT.21884
Related Organisations
Related Funding Activities
Algorithms And Data Structures To Support Automated Analysis Of Trajectory Data
Start Date: 2010
End Date: 2014
Funder: Australian Research Council
View Funded ActivityLocal Re-optimisation For Turbocharging Heuristics
Start Date: 2015
End Date: 2017
Funder: Australian Research Council
View Funded ActivityDevising Tools For Big Data Sets To Support Computational Movement Analysis
Start Date: 2018
End Date: 2020
Funder: Australian Research Council
View Funded ActivityARC Future Fellowships - Grant ID: FT100100755
Start Date: 04-2011
End Date: 04-2016
Amount: $671,342.00
Funder: Australian Research Council
View Funded ActivityDiscovery Projects - Grant ID: DP180102870
Start Date: 06-2018
End Date: 06-2024
Amount: $362,666.00
Funder: Australian Research Council
View Funded ActivityDiscovery Projects - Grant ID: DP150101134
Start Date: 06-2015
End Date: 05-2019
Amount: $355,100.00
Funder: Australian Research Council
View Funded Activity