Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2021.4
URN: urn:nbn:de:0030-drops-127654
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12765/
Besa, Juan Jose ; Johnson, Timothy ; Mamano, Nil ; Osegueda, Martha C.
Taming the Knight’s Tour: Minimizing Turns and Crossings
| pdf-format: |
|
Abstract
We introduce two new metrics of "simplicity" for knight’s tours: the number of turns and the number of crossings. We give a novel algorithm that produces tours with 9.5n+O(1) turns and 13n+O(1) crossings on a n× n board, and we show lower bounds of (6-ε)n and 4n-O(1) on the respective problems of minimizing these metrics. Hence, our algorithm achieves approximation ratios of 19/12+o(1) and 13/4+o(1). We generalize our techniques to rectangular boards, high-dimensional boards, symmetric tours, odd boards with a missing corner, and tours for (1,4)-leapers. In doing so, we show that these extensions also admit a constant approximation ratio on the minimum number of turns, and on the number of crossings in most cases.
BibTeX - Entry
@InProceedings{besa_et_al:LIPIcs:2020:12765,
author = {Juan Jose Besa and Timothy Johnson and Nil Mamano and Martha C. Osegueda},
title = {{Taming the Knight’s Tour: Minimizing Turns and Crossings}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {4:1--4:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Martin Farach-Colton and Giuseppe Prencipe and Ryuhei Uehara},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12765},
URN = {urn:nbn:de:0030-drops-127654},
doi = {10.4230/LIPIcs.FUN.2021.4},
annote = {Keywords: Graph Drawing, Chess, Hamiltonian Cycle, Approximation Algorithms}
}
| Keywords: | Graph Drawing, Chess, Hamiltonian Cycle, Approximation Algorithms | |
| Seminar: | 10th International Conference on Fun with Algorithms (FUN 2021) | |
| Issue date: | 2020 | |
| Date of publication: | 16.09.2020 | |
| Supplementary Material: | https://nmamano.github.io/MinCrossingsKnightsTour/index.html |
