Capturing a convex object with three discs

Jeff Erickson, Shripad Thite, Fred Rothganger, Jean Ponce

Research output: Contribution to journalConference articlepeer-review


This paper addresses the problem of capturing an arbitrary convex object P in the plane with three congruent disc-shaped robots. Given two stationary robots in contact with P, we characterize the set of positions of a third robot that prevent P from escaping to infinity and show that the computation of this so-called capture region reduces to the resolution of a visibility problem. We present two algorithms for solving this problem and computing the capture region when P is a polygon and the robots are points (zero-radius discs). The first algorithm is exact and has polynomial-time complexity. The second one uses simple hidden-surface removal techniques from computer graphics to output an arbitrarily accurate approximation of the capture region; it has been implemented and examples are presented.

Original languageEnglish (US)
Pages (from-to)2242-2247
Number of pages6
JournalProceedings - IEEE International Conference on Robotics and Automation
StatePublished - 2003
Event2003 IEEE International Conference on Robotics and Automation - Taipei, Taiwan, Province of China
Duration: Sep 14 2003Sep 19 2003

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering


Dive into the research topics of 'Capturing a convex object with three discs'. Together they form a unique fingerprint.

Cite this