Document Open Access Logo

Trajectory Visibility

Authors Patrick Eades, Ivor van der Hoog, Maarten Löffler, Frank Staals

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2020.23.pdf
  • Filesize: 0.84 MB
  • 22 pages

Document Identifiers

Author Details

Patrick Eades
  • University of Sydney, Australia
Ivor van der Hoog
  • Utrecht University, the Netherlands
Maarten Löffler
  • Utrecht University, the Netherlands
Frank Staals
  • Utrecht University, the Netherlands

Funding

All authors are partially supported through the University of Sydney – Utrecht University Partnership Collaboration Awards: Algorithms and data structures to support computational movement analysis.
  • van der Hoog, Ivor: Supported by the Netherlands Organisation for Scientific Research (NWO); 614.001.504.
  • Löffler, Maarten: Partially supported by the Netherlands Organisation for Scientific Research (NWO) under project numbers 614.001.504 and 628.011.005.

Cite As Get BibTex

Patrick Eades, Ivor van der Hoog, Maarten Löffler, and Frank Staals. Trajectory Visibility. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SWAT.2020.23

Abstract

We study the problem of testing whether there exists a time at which two entities moving along different piece-wise linear trajectories among polygonal obstacles are mutually visible. We study several variants, depending on whether or not the obstacles form a simple polygon, trajectories may intersect the polygon edges, and both or only one of the entities are moving.
For constant complexity trajectories contained in a simple polygon with n vertices, we provide an 𝒪(n) time algorithm to test if there is a time at which the entities can see each other. If the polygon contains holes, we present an 𝒪(n log n) algorithm. We show that this is tight.
We then consider storing the obstacles in a data structure, such that queries consisting of two line segments can be efficiently answered. We show that for all variants it is possible to answer queries in sublinear time using polynomial space and preprocessing time. 
As a critical intermediate step, we provide an efficient solution to a problem of independent interest: preprocess a convex polygon such that we can efficiently test intersection with a quadratic curve segment. If the obstacles form a simple polygon, this allows us to answer visibility queries in 𝒪(n³/4log³ n) time using 𝒪(nlog⁵ n) space. For more general obstacles the query time is 𝒪(log^k n), for a constant but large value k, using 𝒪(n^{3k}) space. We provide more efficient solutions when one of the entities remains stationary.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • trajectories
  • visibility
  • data structures
  • semi-algebraic range searching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. P. K. Agarwal and J. Matoušek. Dynamic half-space range reporting and its applications. Algorithmica, 13(4):325-345, April 1995. URL: http://dx.doi.org/10.1007/BF01293483.
  2. Pankaj K. Agarwal, Jivr'i Matouvsek, and Micha Sharir. On range searching with semialgebraic sets. II. SICOMP, 42(6):2039-2062, 2013. URL: http://dx.doi.org/10.1137/120890855.
  3. Boris Aronov, Leonidas J Guibas, Marek Teichmann, and Li Zhang. Visibility queries and maintenance in simple polygons. DCG, 27(4):461-483, 2002. Google Scholar
  4. Michael Ben-Or. Lower bounds for algebraic computation trees. In STOC, pages 80-86, 1983. Google Scholar
  5. Marc Benkert, Joachim Gudmundsson, Florian Hübner, and Thomas Wolle. Reporting flock patterns. Comput. Geom., 41(3):111-125, 2008. URL: http://dx.doi.org/10.1016/j.comgeo.2007.10.003.
  6. Marshall Bern, David Dobkin, David Eppstein, and Robert Grossman. Visibility with a moving point of view. Algorithmica, 11(4):360-378, 1994. Google Scholar
  7. P. Bovet and S. Benhamou. Spatial analysis of animals' movements using a correlated random walk model. J. Theoretical Biology, 131(4):419-433, 1988. URL: http://dx.doi.org/10.1016/S0022-5193(88)80038-9.
  8. Gerth Stølting Brodal and Riko Jacob. Dynamic planar convex hull. In FOCS, pages 617-626, 2002. Google Scholar
  9. Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Maarten Löffler, and Jun Luo. Detecting commuting patterns by clustering subtrajectories. IJCGA, 21(03):253-282, 2011. URL: http://dx.doi.org/10.1142/S0218195911003652.
  10. Jean Cardinal and Udo Hoffmann. Recognition and complexity of point visibility graphs. DCG, 57(1):164-178, 2017. Google Scholar
  11. Timothy M Chan. Optimal partition trees. DCG, 47(4):661-690, 2012. Google Scholar
  12. Bernard Chazelle. Cutting hyperplanes for divide-and-conquer. DCG, 9(2):145-158, 1993. Google Scholar
  13. Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, John Hershberger, Micha Sharir, and Jack Snoeyink. Ray shooting in polygons using geodesic triangulations. Algorithmica, 12(1):54-68, 1994. Google Scholar
  14. Bernard Chazelle and Leonidas J. Guibas. Visibility and intersection problems in plane geometry. DCG, 4:551-581, 1989. URL: http://dx.doi.org/10.1007/BF02187747.
  15. Vasek Chvátal. A combinatorial theorem in plane geometry. JCTB, 18(1):39-41, 1975. Google Scholar
  16. Mark De Berg. Ray shooting, depth orders and hidden surface removal, volume 703. Springer Science & Business Media, 1993. Google Scholar
  17. Mark De Berg, Marc Van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational geometry. Springer, 1997. Google Scholar
  18. Yago Diez, Matias Korman, André van Renssen, Marcel Roeloffzen, and Frank Staals. Kinetic all-pairs shortest path in a simple polygon. EuroCG, pages 21-24, 2017. abstract. Google Scholar
  19. David P. Dobkin and David G. Kirkpatrick. Fast detection of polyhedral intersection. TCS, 27(3):241-253, 1983. ICALP. URL: http://dx.doi.org/10.1016/0304-3975(82)90120-7.
  20. Somayeh Dodge, Robert Weibel, and Ehsan Forootan. Revealing the physics of movement: Comparing the similarity of movement characteristics of different types of moving objects. Computers, Environment and Urban Systems, 33(6):419-434, 2009. Google Scholar
  21. James R. Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan. Making data structures persistent. JCSS, 38(1):86-124, 1989. URL: http://dx.doi.org/10.1016/0022-0000(89)90034-2.
  22. Frédo Durand. A multidisciplinary survey of visibility. ACM Siggraph course notes Visibility, Problems, Techniques, and Applications, 2000. Google Scholar
  23. Steve Fisk. A short proof of chvátal’s watchman theorem. JCTB, 24(3):374, 1978. Google Scholar
  24. Leila De Floriani and Paola Magillo. Algorithms for visibility computation on terrains: a survey. Environ. Plann. B, 30(5):709-728, 2003. Google Scholar
  25. S. Gaffney and P. Smyth. Trajectory clustering with mixtures of regression models. In KDD, pages 63-72, 1999. Google Scholar
  26. Subir K. Ghosh and Partha P. Goswami. Unsolved problems in visibility graphs of points, segments, and polygons. CSUR, 46(2):22:1-22:29, December 2013. URL: http://dx.doi.org/10.1145/2543581.2543589.
  27. Joachim Gudmundsson, Patrick Laube, and Thomas Wolle. Movement patterns in spatio-temporal data. In Encyclopedia of GIS., pages 1362-1370. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-17885-1_823.
  28. Leonidas J. Guibas and John Hershberger. Optimal shortest path queries in a simple polygon. J. Comput. Syst. Sci., 39(2):126-152, 1989. URL: http://dx.doi.org/10.1016/0022-0000(89)90041-X.
  29. Leonidas J. Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert Endre Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2:209-233, 1987. URL: http://dx.doi.org/10.1007/BF01840360.
  30. Eliezer Gurarie, Russel D. Andrews, and Kristin L. Laidre. A novel method for identifying behavioural changes in animal movement data. Ecology Letters, 12(5):395-408, 2009. URL: http://dx.doi.org/10.1111/j.1461-0248.2009.01293.x.
  31. Patrick Laube, Marc J. van Kreveld, and Stephan Imfeld. Finding REMO - detecting relative motion patterns in geospatial lifelines. In SDH, pages 201-215, 2004. URL: http://dx.doi.org/10.1007/3-540-26772-7_16.
  32. J.G. Lee, J. Han, and K.Y. Whang. Trajectory clustering: a partition-and-group framework. In Proc. ACM SIGMOD International Conference on Management of Data, pages 593-604, 2007. Google Scholar
  33. Xiaojie Li, Xiang Li, Daimin Tang, and Xianrui Xu. Deriving features of traffic flow around an intersection from trajectories of vehicles. In Proc. 18th International Conference on Geoinformatics, pages 1-5. IEEE, 2010. Google Scholar
  34. J. Matoušek. Efficient partition trees. DCG, 1992. Google Scholar
  35. Jiří Matoušek. Range searching with efficient hierarchical cuttings. DCG, 10(2):157-182, 1993. URL: http://dx.doi.org/10.1007/BF02573972.
  36. Ether Moet. Computation and complexity of visibility in geometric environments. PhD thesis, Utrecht University, 2008. Google Scholar
  37. Ketan Mulmuley. Hidden surface removal with respect to a moving view point. In STOC, pages 512-522. ACM, 1991. Google Scholar
  38. J. Nievergelt and E. M. Reingold. Binary Search Trees of Bounded Balance. SICOMP, 2(1):33-43, 1973. Google Scholar
  39. Joseph O'Rourke. Art Gallery Theorems and Algorithms. Oxford University Press, Inc., New York, NY, USA, 1987. Google Scholar
  40. Michel Pocchiola and Gert Vegter. The visibility complex. IJCGA, 6(3):279-308, 1996. Google Scholar
  41. Andreas Stohl. Computation, accuracy and applications of trajectories - a review and bibliography. Atmospheric Environment, 32(6):947-966, 1998. URL: http://dx.doi.org/10.1016/S1352-2310(97)00457-3.
  42. Emo Welzl. Constructing the visibility graph for n-line segments in o(n²) time. IPL, 20(4):167-171, 1985. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact