Convex hull representations of models for computing collisions between multiple bodies

Hanif D. Sherali, J. Cole Smith, Shokri Z. Selim

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


In this paper, we consider a collision detection problem that frequently arises in the field of robotics. Given a set of bodies with their initial positions and trajectories, we wish to identify the first collision that occurs between any two bodies, or to determine that none exists. For the case of bodies having linear trajectories, we construct a convex hull representation of the integer programming model of S.Z. Selim and H.A. Almohamad [European Journal of Operational Research 119 (1) (1999) 121-129], and compare the relative effectiveness in solving this problem via the resultant linear program. We also extend this analysis to model a situation in which bodies move along piecewise linear trajectories, possibly rotating at the end of each linear segment. For this case, we again compare an integer programming approach with its linear programming convex hull representation, and exhibit the effectiveness of solving a sequence of mathematical programs for each time segment over a global programming scheme which considers all segments at once. We provide computational results to illustrate the effect of various numbers of bodies present in the collision scenarios, as well as the times at which the first collision occurs.

Original languageEnglish (US)
Pages (from-to)514-526
Number of pages13
JournalEuropean Journal of Operational Research
Issue number3
StatePublished - Dec 16 2001
Externally publishedYes


  • Convex hull
  • Integer programming
  • Linear programming
  • Multi-body collision

ASJC Scopus subject areas

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


Dive into the research topics of 'Convex hull representations of models for computing collisions between multiple bodies'. Together they form a unique fingerprint.

Cite this