TY - GEN
T1 - Motion Planning Problems with Boxes
T2 - 2018 International Conference on Control and Robots, ICCR 2018
AU - Toussaint, Godfried T.
N1 - Funding Information:
ACKNOWLEDGMENT This research was generously supported by grant fund No. 76, Program ADHGP, Project AD072, awarded by the Provost’s Office of New York University Abu Dhabi (NYUAD) in Abu Dhabi, The United Arab Emirates.
Publisher Copyright:
© 2018 IEEE.
Copyright:
Copyright 2019 Elsevier B.V., All rights reserved.
PY - 2018/11/13
Y1 - 2018/11/13
N2 - 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.
AB - 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.
KW - algorithms
KW - axis-parallell rectangles
KW - collision aoidance
KW - combinatorial geometry
KW - computational geometry
KW - discrete mathematics
KW - robotics
KW - spatial motion planning
UR - http://www.scopus.com/inward/record.url?scp=85056483764&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85056483764&partnerID=8YFLogxK
U2 - 10.1109/ICCR.2018.8534492
DO - 10.1109/ICCR.2018.8534492
M3 - Conference contribution
AN - SCOPUS:85056483764
T3 - 2018 International Conference on Control and Robots, ICCR 2018
SP - 73
EP - 77
BT - 2018 International Conference on Control and Robots, ICCR 2018
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 15 September 2018 through 17 September 2018
ER -