Fast algorithms for collision and proximity problems involving moving geometric objects | SpringerLink
Skip to main content

Fast algorithms for collision and proximity problems involving moving geometric objects

  • Conference paper
  • First Online:
Algorithms — ESA '94 (ESA 1994)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 855))

Included in the following conference series:

Abstract

Consider a set of geometric objects, such as points or axes-parallel hyperrectangles in ℝd, that move with constant but possibly different velocities along linear trajectories. Efficient algorithms are presented for several problems defined on such objects, such as determining whether any two objects ever collide and computing the minimum inter-point separation or minimum diameter that ever occurs. In particular, two open problems from the literature are solved: Deciding in o(n 2) time if there is a collision in a set of n moving points in ℝ2, where the points move at constant but possibly different velocities, and the analogous problem for detecting a red-blue collision between sets of red and blue moving points. The strategy used involves reducing the given problem on moving objects to a different problem on a set of static objects, and then solving the latter problem using techniques based on sweeping, orthogonal range searching, simplex composition, and parametric search.

The research of these authors was supported in part by NSF grant CCR-92-00270.

This author was supported by the ESPRIT Basic Research Actions Program, under contract No. 7141 (project ALCOM II).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. A. Aggarwal, M. Hansen and T. Leighton. Solving query-retrieval problems by compacting Voronoi diagrams. Proc. 22nd STOC, 1990, 331–340.

    Google Scholar 

  2. S.G. Akl and K.A. Lyons. Parallel computational geometry. Prentice-Hall, Englewood Cliffs, 1993.

    Google Scholar 

  3. M.J. Atallah. Some dynamic computational geometry problems. Computers and Mathematics with Applications 11 (1985), pp. 1171–1181.

    Article  MATH  MathSciNet  Google Scholar 

  4. B. Chazelle, H. Edelsbrunner, L. Guibas and M. Sharir. Diameter, width, closest line pair, and parametric searching. Proc. 8th ACM Symp. Computational Geometry, 1992, 120–129.

    Google Scholar 

  5. J.-J. Fu and R.C.T. Lee. Voronoi diagrams of moving points in the plane. Intern. J. of Computational Geometry & Applications 1 (1991), pp. 23–32.

    MathSciNet  Google Scholar 

  6. J.-J. Fu and R.C.T. Lee. Minimum spanning trees of moving points in the plane. IEEE Transactions on Computers 40 (1991), pp. 113–118.

    MathSciNet  Google Scholar 

  7. K. Fujimura. Motion planning in dynamic environments. Springer-Verlag, 1991.

    Google Scholar 

  8. M.J. Golin, C. Schwarz and M. Smid. Further dynamic computational geometry. Proc. 4th Canadian Conf. on Computational Geometry, 1992, 154–159.

    Google Scholar 

  9. P. Gupta, R. Janardan and M. Smid. Fast algorithms for collision and proximity problems involving moving geometric objects. Report MPI-I-94-113, Max-Planck-Institut für Informatik, Saarbrücken, 1994.

    Google Scholar 

  10. D.P. Huttenlocher, K. Kedem and J.M. Kleinberg. On dynamic Voronoi diagrams and the minimum Hausdorff distance for point sets under Euclidean motion in the plane. Proc. 8th ACM Symp. on Computational Geometry, 1992, 110–119.

    Google Scholar 

  11. M. van Kreveld. New results on data structures in computational geometry. Ph.D. Thesis, University of Utrecht, The Netherlands, 1992.

    Google Scholar 

  12. J. Matoušek. Range searching with efficient hierarchical cuttings. Discrete & Computational Geometry 10 (1993), pp. 157–182.

    MathSciNet  Google Scholar 

  13. N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms. Journal of the ACM 30 (1983), pp. 852–865.

    Article  MATH  MathSciNet  Google Scholar 

  14. C.L. Monma and S. Suri. Transitions in geometric minimum spanning trees. Proc. 7th ACM Symp. on Computational Geometry, 1991, 239–249.

    Google Scholar 

  15. T. Ottmann and D. Wood. Dynamic sets of points. Computer Vision, Graphics and Image Processing 27 (1984), pp 157–166.

    MathSciNet  Google Scholar 

  16. M. Pellegrini. Incidence and nearest-neighbor problems for lines in 3-space. Proc. 8th ACM Symp. on Computational Geometry, 1992, 130–137.

    Google Scholar 

  17. F.P. Preparata and M.I. Shamos. Computational geometry, an introduction. Springer-Verlag, 1988.

    Google Scholar 

  18. D.E. Willard and G.S. Lueker. Adding range restriction capability to dynamic data structures. Journal of the ACM 32 (1985), pp. 597–617.

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Jan van Leeuwen

Rights and permissions

Reprints and permissions

Copyright information

© 1994 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Gupta, P., Janardan, R., Smid, M. (1994). Fast algorithms for collision and proximity problems involving moving geometric objects. In: van Leeuwen, J. (eds) Algorithms — ESA '94. ESA 1994. Lecture Notes in Computer Science, vol 855. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0049415

Download citation

  • DOI: https://doi.org/10.1007/BFb0049415

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-58434-6

  • Online ISBN: 978-3-540-48794-4

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics