TY - GEN
T1 - Matchstick games
T2 - 2nd International conference on Europe Middle East and North Africa Information Systems and Technologies to support Learning, EMENA-ISTL 2018
AU - Toussaint, Godfried T.
N1 - Funding Information:
Acknowledgments. This research was supported by a grant from the Provost’s Office, administered by the Faculty of Science of New York University Abu Dhabi, in Abu Dhabi, The United Arab Emirates.
Publisher Copyright:
© Springer Nature Switzerland AG 2019.
PY - 2019
Y1 - 2019
N2 - It is shown that given any configuration of n ≥ 3 line segments (matchsticks) in the plane, there exist at least three segments that can each be translated to infinity, without colliding with the other n − 1 segments. In addition, if n ≥ 4, and the line segments are restricted to be parallel to the axes, at least four segments can be moved without disturbing the others. Furthermore, both lower bounds are best possible. The proofs are elementary and suitable for teaching in lower-level undergraduate courses on discrete mathematics.
AB - It is shown that given any configuration of n ≥ 3 line segments (matchsticks) in the plane, there exist at least three segments that can each be translated to infinity, without colliding with the other n − 1 segments. In addition, if n ≥ 4, and the line segments are restricted to be parallel to the axes, at least four segments can be moved without disturbing the others. Furthermore, both lower bounds are best possible. The proofs are elementary and suitable for teaching in lower-level undergraduate courses on discrete mathematics.
KW - Artificial intelligence
KW - Collision avoidance
KW - Computational geometry
KW - Discrete mathematics
KW - Line segments
KW - Robotics
KW - Spatial planning
KW - Translation
UR - http://www.scopus.com/inward/record.url?scp=85056475862&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85056475862&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-03577-8_63
DO - 10.1007/978-3-030-03577-8_63
M3 - Conference contribution
AN - SCOPUS:85056475862
SN - 9783030035761
T3 - Smart Innovation, Systems and Technologies
SP - 580
EP - 587
BT - Information Systems and Technologies to Support Learning - Proceedings of EMENA-ISTL 2018
A2 - Rocha, Alvaro
A2 - Serrhini, Mohammed
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 25 October 2018 through 27 October 2018
ER -