Algorithmic issues in modeling motion

ABSTRACT

This article is a survey of research areas in which motion plays a pivotal role. The aim of the article is to review current approaches to modeling motion together with related data structures and algorithms, and to summarize the challenges that lie ahead in producing a more unified theory of motion representation that would be useful across several disciplines.

REFERENCES

• 1: Pankaj K. Agarwal , Lars Arge , Jeff Erickson, Indexing moving points (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.175-186, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335220]
• 2: Agarwal, P. K., Basch, J., Guibas, L. J., Hershberger, J., and Zhang, L. 2000. Deformable free space tiling for kinetic collision detection. In Proc. 4th Workshop Algorithmic Found. Robot., to appear.
• 3: Agarwal, P. K. and Erickson, J. 1999. Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry, B. Chazelle, J. E. Goodman, and R. Pollack, eds. Contemporary Mathematics, vol. 223. American Mathematical Society, R.I., pp. 1--56.
• 4: Pankaj K. Agarwal , Leonidas J. Guibas , John Hershberger , Eric Veach, Maintaining the Extent of a Moving Point Set, Proceedings of the 5th International Workshop on Algorithms and Data Structures, p.31-44, August 06-08, 1997
• 5: Pankaj K. Agarwal , Sariel Hal-Peled, Maintaining approximate extent measures of moving points, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.148-157, January 07-09, 2001, Washington, D.C., United States
• 6: Agarwal, P. K. and Procopiuc, C. M. 2002. Advances in indexing mobile objects. IEEE Bull. Data Eng. 25, 25--34.
• 7: Agarwal, P. K. and Sharir, M. 2000. Arrangements and their applications. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds. Elsevier Science Publishers B.V. North-Holland, Amsterdam, The Netherlands, pp. 49--119.
• 8: Alm, E. and Baker, D. 1999. Prediction of protein-folding mechanisms from free-energy landscapes derived from native structures. Proc. Nat. Acad. Sci. USA, 96, 11305--11310.
• 9: Amadei, A., Linssen, B. M., and Berendsen, H. J. C. 1993. Essential dynamics of protein. Proteins: Structure, Function, and Genetics 17, 412--425.
• 10: Nancy M. Amato , Ken A. Dill , Guang Song, Using motion planning to map protein folding landscapes and analyze folding kinetics of known native structures, Proceedings of the sixth annual international conference on Computational biology, p.2-11, April 18-21, 2002, Washington, DC, USA [doi>10.1145/565196.565198]
• 11: Mehmet Serkan Apaydin , Douglas L. Brutlag , Carlos Guestrin , David Hsu , Jean-Claude Latombe, Stochastic roadmap simulation: an efficient representation and algorithm for analyzing molecular motion, Proceedings of the sixth annual international conference on Computational biology, p.12-21, April 18-21, 2002, Washington, DC, USA [doi>10.1145/565196.565199]
• 12: Apaydin, M., Singh, A., Brutlag, D., and Latombe, J. 2001. Capturing molecular energy landscapes with probabilistic conformational roadmaps. In Proceedings of the IEEE Conference on Robotics and Automation.
• 13: Arulampalam, S., Maskell, S., Gordon, N., and Clapp, T. 2002. A tutorial on particle filters for on-line non-linear/non-gaussian bayesian tracking. IEEE Trans. Sig. Proc. 50, 174--188.
• 14: Atallah, M. J. 1985. Some dynamic computational geometry problems. Comput. Math. Appl. 11, 1171--1181.
• 15: D. Baraff, Analytical methods for dynamic simulation of non-penetrating rigid bodies, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.223-232, July 1989
• 16: David Baraff , Andrew Witkin, Large steps in cloth simulation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.43-54, July 1998 [doi>10.1145/280814.280821]
• 17: Jérîme Barraquand , Jean-Claude Latombe, Robot motion planning: a distributed representation approach, International Journal of Robotics Research, v.10 n.6, p.628-649, Dec. 1991 [doi>10.1177/027836499101000604]
• 18: Julien Basch , Leonidas J. Guibas , John Hershberger, Data structures for mobile data, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.747-756, January 05-07, 1997, New Orleans, Louisiana, United States
• 19: Bern, M. and Plassmann, P. 2000. Mesh generation. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds. Elsevier Science Publishers, B. V. North-Holland, Amsterdam, The Netherlands, 291--332.
• 20: Michael J. Black , Yaser Yacoob, Recognizing Facial Expressions in Image Sequences Using Local Parameterized Models of Image Motion, International Journal of Computer Vision, v.25 n.1, p.23-48, Oct. 1997 [doi>10.1023/A:1007977618277]
• 21: Michael J. Black , Allan D. Jepson, EigenTracking: Robust Matching and Tracking of Articulated Objects Using a View-Based Representation, International Journal of Computer Vision, v.26 n.1, p.63-84, Jan. 1998 [doi>10.1023/A:1007939232436]
• 22: A. Blake , B. North , M. Isard, Learning multi-class dynamics, Proceedings of the 1998 conference on Advances in neural information processing systems II, p.389-395, July 1999
• 23: Bonnet, P., Gehrke, J. E., and Seshadri, P. 2000. Querying the physical world. IEEE Pers. Commun. 7, 10--15.
• 24: Philippe Bonnet , Johannes Gehrke , Praveen Seshadri, Towards Sensor Database Systems, Proceedings of the Second International Conference on Mobile Data Management, p.3-14, January 08-10, 2001
• 25: Robert Bridson , Ronald Fedkiw , John Anderson, Robust treatment of collisions, contact and friction for cloth animation, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 26: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 27: Brown, J., Sorkin, S., Bruyns, C., Latombe, J.-C., Montgomery, K., and Stephanides, M. 2001. Real-time simulation of deformable objects: Tools and application. Proc. Comput. Animat.
• 28: Bryant, R., Edelsbrunner, H., Koehl, P., and Levitt, M. 2000. Inclusion-exclusion formulas for the area derivative of a space-filling diagram. manuscript.
• 29: Ting Chen , Dimitris N. Metaxas, Image Segmentation Based on the Integration of Markov Random Fields and Deformable Models, Proceedings of the Third International Conference on Medical Image Computing and Computer-Assisted Intervention, p.256-265, October 11-14, 2000
• 30: Cheng, H.-L., Dey, T. K., Edelsbrunner, H., and Sullivan, J. 2001. Dynamic skin triangulation. Disc. Comput. Geom. 25, 525--568.
• 31: Jan Chomicki , Peter Z. Revesz, A Geometric Framework for Specifying Spatiotemporal Objects, Proceedings of the Sixth International Workshop on Temporal Representation and Reasoning, p.41, May 01-02, 1999
• 32: Cockburn, B., Karniadakis, G., and Shu, C. W. 2000. Discontinuous Galerkin Methods: Theory, Computation and Applications. Springer-Verlag, New York.
• 33: Gilles Debunne , Mathieu Desbrun , Marie-Paule Cani , Alan H. Barr, Dynamic real-time deformations using space & time adaptive sampling, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.31-36, August 2001 [doi>10.1145/383259.383262]
• 34: Douglas Decarlo , Dimitris Metaxas, Optical Flow Constraints on Deformable Models with Applications to Face Tracking, International Journal of Computer Vision, v.38 n.2, p.99-127, July 2000 [doi>10.1023/A:1008122917811]
• 35: Dill, K. A., Bromberg, S., Yue, K. Z., and Fiebig, K. M. 1995. Principles of protein folding. a perspective from simple exact models. Protein Sci. 4, 561--602.
• 36: H. Edelsbrunner , D. Letscher , A. Zomorodian, Topological persistence and simplification, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.454, November 12-14, 2000
• 37: Erickson, J., Guoy, D., Sullivan, J. M., and Üngör, A. 2002. Building space-time meshies over arbitrary spatial domains. In Proceedings of the 11th International Meshing Roundtable, 391--402.
• 38: Gao, J., Guibas, L., Hershberger, J., Zhang, L., and Zhu, A. 2001. Discrete mobile centers. Manuscript.
• 39: Leonidas Guibas , An Nguyen , Daniel Russel , Li Zhang, Collision detection for deforming necklaces, Proceedings of the eighteenth annual symposium on Computational geometry, p.33-42, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513405]
• 40: Dan Halperin , Lydia Kavraki , Jean-Claude Latombe, Robotics, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 41: Richard Hartley , Andrew Zisserman, Multiple view geometry in computer visiond, Cambridge University Press, New York, NY, 2001
• 42: Michael Isard , Andrew Blake, C$ONDENSATION$—Conditional Density Propagation forVisual Tracking, International Journal of Computer Vision, v.29 n.1, p.5-28, Aug. 1998 [doi>10.1023/A:1008078328650]
• 43: Simon Kahan, A model for data in motion, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.265-277, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103449]
• 44: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 45: Lydia E. Kavraki , Jean-Claude Latombe , Rajeev Motwani , Prabhakar Raghavan, Randomized query processing in robot path planning, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.353-362, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225159]
• 46: Kavraki, L. E., Ŝvestka, P., Latombe, J.-C., and Overmars, M. H. 1996. Probabilistic roadmaps for path planning in high dimensional configuration spaces. IEEE Trans. Robot. Autom. 12, 566--580.
• 47: David Kirkpatrick , Jack Snoeyink , Bettina Speckmann, Kinetic collision detection for simple polygons, Proceedings of the sixteenth annual symposium on Computational geometry, p.322-330, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336219]
• 48: David Kirkpatrick , Jack Snoeyink , Bettina Speckmann, Kinetic collision detection for simple polygons, Proceedings of the sixteenth annual symposium on Computational geometry, p.322-330, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336219]
• 49: David Kirkpatrick , Bettina Speckmann, Kinetic maintenance of context-sensitive hierarchical representations for disjoint simple polygons, Proceedings of the eighteenth annual symposium on Computational geometry, p.179-188, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513423]
• 50: Paul G. Kry , Dinesh K. Pai, Continuous contact simulation for smooth surfaces, ACM Transactions on Graphics (TOG), v.22 n.1, p.106-129, January 2003 [doi>10.1145/588272.588280]
• 51: Lamiraux, F. and Kavraki, L. 2001. Planning paths for elastic objects under manipulation constraints. Int. J. Roboti. Res. 20, 188--208.
• 52: Lang, J., Pai, D. K., and Woodham, R. J. 2002. Robotic acquisition of deformable models. In Proceedings of the IEEE International Conference on Robotics and Automation. pp. 933--938.
• 53: Larson, E., Gottschalk, S., Lin, M., and Manocha, D. 2000. Fast distance queries using rectangular swept sphere volume. In Proceedings of the IEEE International Conference on Robotics and Automation, 3719--3726.
• 54: Joseph Laszlo , Michiel van de Panne , Eugene Fiume, Interactive control for physically-based animation, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.201-208, July 2000 [doi>10.1145/344779.344876]
• 55: Jean-Claude Latombe, Robot Motion Planning, Kluwer Academic Publishers, Norwell, MA, 1991
• 56: Leach, A. R. 1996. Molecular Modeling: Principles and Applications. Addison-Welsley Longman, Rssex, England.
• 57: Levitt, M., Gerstein, M., Huang, E., Subbiah, S., and Tsai, J. 1997. Protein folding: The endgame. Ann. Rev. Biochem. 66, 549--579.
• 58: Lin, M. and Gottschalk, S. 1998. Collision detection between geometric models: A survey. In Proceedings of the IMA Conference on Mathematics of Surfaces.
• 59: Tony Lindeberg, Scale-Space Theory in Computer Vision, Kluwer Academic Publishers, Norwell, MA, 1994
• 60: Longuet-Higgins, H. C. 1981. A computer algorithm for reconstructing a scene from two projections. Nature 293, 133--135.
• 61: Lotstedt, P. 1981. Coulomb friction in two-dimensional rigid body systems. ZAMM 61, 605--613.
• 62: Lowrie, R. B., Roe, P. L., and van Leer, B. 1998. Space-time methods for hyperbolic conservation laws. In Barriers and Challenges in Computational Fluid Dynamics. ICASE/LaRC Interdisciplinary Series in Science and Engineering, vol. 6. Kluwer, pp. 79--98.
• 63: Matthew T. Mason, Mechanics of robotic manipulation, MIT Press, Cambridge, MA, 2001
• 64: Jiří Matoušek, Geometric range searching, ACM Computing Surveys (CSUR), v.26 n.4, p.422-461, Dec. 1994 [doi>10.1145/197405.197408]
• 65: Meyer, M., Debunne, G., Desbrun, M., and Barr, A. H. 2001. Interactive animation of cloth-like objects in virtual reality. J. Vis. Comput. Animat. 12, 1--12.
• 66: Brian Vincent Mirtich, Impulse-based dynamic simulation of rigid body systems, 1996
• 67: Brian Mirtich, V-Clip: fast and robust polyhedral collision detection, ACM Transactions on Graphics (TOG), v.17 n.3, p.177-208, July 1998 [doi>10.1145/285857.285860]
• 68: Brian Mirtich, Timewarp rigid body simulation, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.193-200, July 2000 [doi>10.1145/344779.344866]
• 69: Onuchic, J. N., Luthey-Schulten, Z., and Wolynes, P. G. 1997. Theory of protein folding: The energy landscape perspective. Ann. Rev. Phys. Chem. 48, 545--600.
• 70: Dinesh K. Pai , Kees van den Doel , Doug L. James , Jochen Lang , John E. Lloyd , Joshua L. Richmond , Som H. Yau, Scanning physical interaction behavior of 3D objects, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.87-96, August 2001 [doi>10.1145/383259.383268]
• 71: Dieter Pfoser , Christian S. Jensen , Yannis Theodoridis, Novel Approaches in Query Processing for Moving Object Trajectories, Proceedings of the 26th International Conference on Very Large Data Bases, p.395-406, September 10-14, 2000
• 72: Richmond, J. L. and Pai, D. K. 2000. Active measurement and modeling of contact sounds. In Proceedings of the IEEE International Conference on Robotics and Automation. pp. 2146--2152.
• 73: Gerard R. Richter, An explicit finite element method for the wave equation, Applied Numerical Mathematics, v.16 n.1-2, p.65-80, Dec. 1994 [doi>10.1016/0168-9274(94)00048-4]
• 74: Royer, E. and Toh, C. 1999. A review of current routing protocols for ad-hoc mobile wireless networks. IEEE Pers. Commun. 6, 46--55.
• 75: Simonas Šaltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez, Indexing the positions of continuously moving objects, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.331-342, May 15-18, 2000, Dallas, Texas, United States
• 76: Schirra, S. 2000. Robustness and precision issues in geometric computation. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds. Elsevier Science Publishers, B. V. North-Holland, Amsterdam, The Netherlands, pp. 597--632.
• 77: A. Prasad Sistla , Ouri Wolfson, Temporal conditions and integrity constraints in active database systems, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.269-280, May 22-25, 1995, San Jose, California, United States
• 78: A. Prasad Sistla , Ouri Wolfson , Sam Chamberlain , Son Dao, Modeling and Querying Moving Objects, Proceedings of the Thirteenth International Conference on Data Engineering, p.422-432, April 07-11, 1997
• 79: Song, G. and Amato, N. M. 2002. Using motion planning to study protein folding pathways. J. Comput. Biol. 9, 149--168.
• 80: Sorenson, H. 1985. Kalman Filtering: Theory and Applications. IEEE Press.
• 81: Tayeb, J., Ulusoy, O., and Wolfson, O. 1998. A quadtree-based dynamic attribute indexing method. Comput. J., 185--200.
• 82: Teodoro, M., Phillips, G., and Kavraki, L. 2000. Singular value decomposition of protein conformational motions: Application to HIV-1 protease. In Currents in Computational Molecular Biology. Universal Academy Press Inc., Tokyo, Japan, pp. 198--199.
• 83: Philip H. S. Torr , Richard Szeliski , P. Anandan, An Integrated Bayesian Approach to Layer Extraction from Image Sequences, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.3, p.297-303, March 2001 [doi>10.1109/34.910882]
• 84: Üngör, A. and Sheffer, A. 2002. Pitching tents in space-time: Mesh generation for discontinuous Galerkin method. Int. J. Found. Comput. Sci. 13, 201--222.
• 85: Üngör, A., Sheffer, A., Haber, R. B., and Teng, S.-H. 2002. Layer based solutions for constrained space-time meshing. Appl. Numer. Math., to appear.
• 86: Kees van den Doel , Paul G. Kry , Dinesh K. Pai, FoleyAutomatic: physically-based sound effects for interactive simulation and animation, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.537-544, August 2001 [doi>10.1145/383259.383322]
• 87: Vogler, C. and Metaxas, D. 2000. A linguistics-based approach to american sign language recognition. In Proceedings of the International Conference on Gestures: Meaning and Use.
• 88: Ouri Wolfson , Sam Chamberlain , Son Dao , Liqin Jiang , Gisela Mendez, Cost and Imprecision in Modeling the Position of Moving Objects, Proceedings of the Fourteenth International Conference on Data Engineering, p.588-596, February 23-27, 1998
• 89: Ouri Wolfson , Liqin Jiang , A. Prasad Sistla , Sam Chamberlain , Naphtali Rishe , Minglin Deng, Databases for Tracking Mobile Units in Real Time, Proceeding of the 7th International Conference on Database Theory, p.169-186, January 10-12, 1999
• 90: Ouri Wolfson , Prasad Sistla , Bo Xu , Jutai Zhou , Sam Chamberlain, DOMINO: databases fOr MovINg Objects tracking, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.547-549, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 91: Yin., L., Acharya., A., Sobh, N., Haber, R. B., and Tortorelli, D. A. 2000. A space-time discontinuous Galerkin method for elastodynamic analysis. In Discontinuous Galerkin Methods: Theory, Computation and Applications, B. Cockburn, G. Karniadakis, and C. Shu, Eds. Lecture Notes in Computational Science and Engineering, vol. 11. Springer-Verlag, New York, pp. 459--464.
• 92: C. B. Zilles , J. K. Salisbury, A constraint-based god-object method for haptic display, Proceedings of the International Conference on Intelligent Robots and Systems-Volume 3, p.3146, August 05-09, 1995

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Geometrical problems and computations

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis
          Subjects: Motion
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms

Keywords:
Computational geometry, computer vision, mobile networks, modeling, molecular biology, motion modeling, physical simulation, robotoics, spatio-temporal databases