Applicant
Prof. Dr. Jörg Arndt
Fakultät Elektrotechnik Feinwerktechnik Informationstechnik
TH Nürnberg
Project Summary
Plane-filling curves are of great relevance for technical and algorithmic applications. Examples are cache-oblivious memory access patterns, improved halftoning algorithms, and good heuristics for the travelling salesman problem.
The first discussion of a curve on the triangular grid by Davis and Knuth. In 2013 only a handful of curves on the triangular grid was known. A search done prior to this project determined about 3500 edge-covering curves on the triangular grid. Our goal was to determine significantly more curves.
The existing software could not be used to take the search further due to combinatorial explosion. The upper bound is O(3n) and it would have taken dozens of CPU years to extend the search to just a few more families of curves. We needed to develop faster algorithms allowing parallelization. The funding was used for that development and doing the computations at the Regionales Rechenzentrum Erlangen (RRZE).