Motion Planning Problems with Boxes: An Introduction for Undergraduate Courses in Discrete Mathematics

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Solutions of simple motion planning problems inoling collections of orthogonal rectangles in the plane, and orthogonal boxes in 3-dimensional space are described. Proofs of seeral theorems regarding collision-free translation properties of these objects are deried. A new elementary simple proof is gien that for each quadrant in the plane, eery collection of orthogonal rectangles admits precisely one ordering that is alid for collision-free translation of the rectangles in eery fixed direction contained in that quadrant. In addition, it is proed that for eery configuration of n greater than 3 orthogonal rectangles in the plane, at least four of them hae the property that each can be translated independently to infinity in some direction, without disturbing the other n-1 rectangles. The proofs are elementary, and therefore suitable for motiating undergraduate computer science students in courses on discrete mathematics. A list of more challenging adanced problems is also proided.

Original languageEnglish (US)
Title of host publication2018 International Conference on Control and Robots, ICCR 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages73-77
Number of pages5
ISBN (Electronic)9781538682432
DOIs
StatePublished - Nov 13 2018
Event2018 International Conference on Control and Robots, ICCR 2018 - Hong Kong, Hong Kong
Duration: Sep 15 2018Sep 17 2018

Publication series

Name2018 International Conference on Control and Robots, ICCR 2018

Other

Other2018 International Conference on Control and Robots, ICCR 2018
CountryHong Kong
CityHong Kong
Period9/15/189/17/18

Keywords

  • algorithms
  • axis-parallell rectangles
  • collision aoidance
  • combinatorial geometry
  • computational geometry
  • discrete mathematics
  • robotics
  • spatial motion planning

ASJC Scopus subject areas

  • Mechanical Engineering
  • Control and Optimization
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Motion Planning Problems with Boxes: An Introduction for Undergraduate Courses in Discrete Mathematics'. Together they form a unique fingerprint.

Cite this