# Knot Datasets: Knot128 & Trefoil100

#### Chris Yu, Henrik Schumacher, Keenan Crane

_version 1.0 — June 12, 2020_

This archive contains two datasets meant to serve as a stress test for knot untangling algorithms.  Each dataset is comprised of highly random embeddings of knots in different classes; the challenge is to untangle these knots into the simplest possible configuration.  Of course, there are many possible definitions of "simplest" (e.g., different knot energies, or other criteria); the purpose of this dataset is simply to provide a standard set of examples on which to benchmark any given task.  This data was originally generated as evaluation for a paper on using knot energies for computational design [1].

### Knot128

The `Knot128` dataset is comprised of 128 knots from distinct knot classes.  The `original/` subdirectory contains a simple prototype of each knot (from _KnotPlot_'s "Knot zoo"); the `perturbed/` subdirectory contains a random embedding from the same isotopy class.  Note that the original and perturbed knots will in general have a different number of vertices, since additional detail may have been added to the knot during randomization.

### Trefoil100

The `Trefoil100` dataset contains 100 random embeddings of the trefoil knot, i.e., all knots in this set belong to the same isotopy class, and should ideally yield the same symmetric minimizer.

### File formats

All knots are stored in the Wavefront OBJ file format.  Note, however, that they use a feature that may not be well-supported by all file readers: rather than storing triangles, they contain a list of edges (just a pair of vertices).  More precisely, each file has a list of vertex coordinates

~~~
v x1 y1 z1
v x2 y2 z2
...
~~~

and a list of edges

~~~
l v1i v1j
l v2i v2j
...
~~~

where `vpi` and `vpj` are 1-based indices into the list of vertex coordinates, specifying the two endpoints _i_ and _j_ of edge _p_.  Any that lines starting with a hash symbol are comments, and can be ignored.

Since this data is stored in plain text, it should be easy to convert to any other target format.

### Notes

In order to generate random embeddings of knots with fixed isotopy classes, we used _KnotPlot_ [1] to randomly perturb knots in a non-intersecting manner, starting from the canonical embeddings provided in _KnotPlot_'s "knot zoo." A strong thermal energy combined with a weak elastic energy was used to randomize the initial configurations.  For reference, the _KnotPlot_ script used to randomize a given knot is included as `randomize_knot.kps`.

For `Knot128` we used the first 128 entries of _KnotPlot_'s knot zoo; for `Trefoil128` we generated 100 random embeddings from the same initial trefoil embedding. All of these knots were intentionally sampled to be difficult in terms of geometric complexity; this was achieved by setting a minimum threshold on the file size (which is almost directly proportional to the vertex count) of the curves exported by _KnotPlot_, and resampling all generated knots until they exceeded this threshold. The threshold chosen was 60 KB, which corresponds to about 1500 vertices.  A histogram of knot sizes can be found in `EdgeCounts.pdf`

[1] Chris Yu, Henrik Schumacher, Keenan Crane, _"Repulsive Curves."_ ACM Transactions on Graphics. (2021).

[2] Robert Scharein, _"KnotPlot."_ Program for drawing, visualizing, manipulating, and energy minimizing knots. See <http://www.knotplot.com> (1998).

