Analyzing Trajectory Gaps to Find Possible Rendezvous Region

Arun Sharma, Shashi Shekhar

Research output: Contribution to journalArticlepeer-review


Given trajectory data with gaps, we investigate methods to identify possible rendezvous regions. The problem has societal applications such as improving maritime safety and regulatory enforcement. The challenges come from two aspects. First, gaps in trajectory data make it difficult to identify regions where moving objects may have rendezvoused for nefarious reasons. Hence, traditional linear or shortest path interpolation methods may not be able to detect such activities, since objects in a rendezvous may have traveled away from their usual routes to meet. Second, user detecting a rendezvous regions involve a large number of gaps and associated trajectories, making the task computationally very expensive. In preliminary work, we proposed a more effective way of handling gaps and provided examples to illustrate potential rendezvous regions. In this article, we are providing detailed experiments with both synthetic and real-world data. Experiments on synthetic data show that the accuracy improved by 50 percent, which is substantial as compared to the baseline approach. In this article, we propose a refined algorithm Temporal Selection Search for finding a potential rendezvous region and finding an optimal temporal range to improve computational efficiency. We also incorporate two novel spatial filters: (i) a Static Ellipse Intersection Filter and (ii) a Dynamic Circle Intersection Spatial Filter. Both the baseline and proposed approaches account for every possible rendezvous pattern. We provide a theoretical evaluation of the algorithms correctness and completeness along with a time complexity analysis. Experimental results on synthetic and real-world maritime trajectory data show that the proposed approach substantially improves the area pruning effectiveness and computation time over the baseline technique. We also performed experiments based on accuracy and precision on synthetic dataset on both proposed and baseline techniques.

Original languageEnglish (US)
Article number36
JournalACM Transactions on Intelligent Systems and Technology
Issue number3
StatePublished - Jun 2022

Bibliographical note

Funding Information:
This research is funded by an academic grant from the National Geospatial-Intelligence Agency (Award No. HM0476-20-1-0009, Project Title: Identifying Aberration Patterns in Multi-attribute Trajectory Data with Gaps). Approved for public release, 21-403. Authors’ address: A. Sharma and S. Shekhar, University of Minnesota, Twin Cities, Minneapolis, Minnesota, USA; emails:, Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from © 2022 Copyright held by the owner/author(s). Publication rights licensed to ACM. 2157-6904/2022/01-ART36 $15.00

Publisher Copyright:
© 2022 held by the owner/author(s). Publication rights licensed to ACM.


  • Spatial data mining
  • time geography
  • trajectory mining


Dive into the research topics of 'Analyzing Trajectory Gaps to Find Possible Rendezvous Region'. Together they form a unique fingerprint.

Cite this