Maximum physically consistent trajectories

Bram Custers, Mees van de Kerkhof, Wouter Meulemans, Bettina Speckmann, Frank Staals

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
28 Downloads (Pure)


Trajectories are usually collected with physical sensors, which are prone to errors and cause outliers in the data. We aim to identify such outliers via the physical properties of the tracked entity, that is, we consider its physical possibility to visit combinations of measurements. We describe optimal algorithms to compute maximum subsequences of measurements that are consistent with (simplified) physics models. Our results are output-sensitive with respect to the number k of outliers in a trajectory of n measurements. Specifically, we describe an O(n logn log 2k) time algorithm for 2D trajectories using a model with unbounded acceleration but bounded velocity, and an O(nk) time algorithm for any model where consistency is "concatenable": a consistent subsequence that ends where another begins together form a consistent sequence. We also consider acceleration-bounded models which are not concatenable. We show how to compute the maximum subsequence for such models in O(nk 2logk) time, under appropriate realism conditions. Finally, we experimentally explore the performance of our algorithms on several large real-world sets of trajectories. Our experiments show that we are generally able to retain larger fractions of noisy trajectories than previous work and simpler greedy approaches. We also observe that the speed-bounded model may in practice approximate the acceleration-bounded model quite well, though we observed some variation between datasets.

Original languageEnglish
Title of host publicationSIGSPATIAL '19: Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
EditorsFarnoush Banaei-Kashani, Goce Trajcevski, Ralf Hartmut Guting, Lars Kulik, Shawn Newsam
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Number of pages10
ISBN (Electronic)9781450369091
ISBN (Print)978-1-4503-6909-1
Publication statusPublished - 5 Nov 2019
Event27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems - Chicago, IL, United States
Duration: 5 Nov 20198 Dec 2019


Conference27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
Abbreviated titleACM SIGSPATIAL 2019
Country/TerritoryUnited States
CityChicago, IL
Internet address


  • Algorithms
  • Experiments
  • Outlier detection
  • Physics models


Dive into the research topics of 'Maximum physically consistent trajectories'. Together they form a unique fingerprint.

Cite this