A linear programming solution for exact collision detection

Ali Akgunduz*, Prashant Banerjee, Sanjay Mehrotra

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


This paper addresses the issue of real-time collision detection between pairs of convex polyhedral objects undergoing fast rotational and translational motions. Accurate contact information between objects in virtual reality based simulations such as product design, assembly analysis, performance testing and ergonomic analysis of products are critical factors to explore when desired realism is to be achieved. For this purpose, fast, accurate and robust collision detection algorithms are required. The method described in the text models the exact collision detection problem between convex objects as a linear program. One of the strengths of the proposed methodology is its capability of addressing high speed interframe collision. In addition to the interframe collision detection, experimental data demonstrate that mathematical programming approaches offer promising results in terms of speed and robustness as well.

Original languageEnglish (US)
Pages (from-to)48-55
Number of pages8
JournalJournal of Computing and Information Science in Engineering
Issue number1
StatePublished - Mar 2005


  • Interframe Collision Detection
  • Linear Programming
  • Primal-Dual Interior-Point Method
  • Virtual Reality

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'A linear programming solution for exact collision detection'. Together they form a unique fingerprint.

Cite this