{
  "annotation_id": "d75addcd-43e7-4d0b-b819-5b143cd9bb28",
  "date_created": "2026-02-17T05:53:04.267000Z",
  "date_modified": "2026-02-17T05:53:04.267000Z",
  "file_hash": "4370b38f55cbff90fb14237651f806f8edb0d0b9104eeec6f291bb6d1c49b00b",
  "private": false,
  "record": {
    "abstract": "We introduce two novel algorithms for the problem of finding the closest pair in a cloud of $n$ points based on findings from mathematical optimal packing theory. Both algorithms are deterministic, show fast effective runtimes, and are very easy to implement. For our main algorithm, cppMM, we prove $O(n)$ time complexity for the case of uniformly distributed points. Our second algorithm, cppAPs, is almost as simple as the brute-force approach, but exhibits an extremely fast empirical running time, although its worst-case time complexity is also $O(n^2)$. We embed the new algorithms in a review of the most prominent contenders and empirically demonstrate their runtime behavior for problem sizes up to $n =$ 33,554,432 points observed in our C++ test environment. For large $n$, cppMM dominates the other algorithms under study.",
    "arxiv_id": "2601.05681",
    "authors": [
      "Martin Hitz",
      "Michaela Hitz"
    ],
    "categories": [
      "cs.DS"
    ],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "title": "On the closest pair of points problem",
    "url": "https://arxiv.org/abs/2601.05681",
    "version": "v1"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "9c07e034-398a-473f-a972-8be3e5fd9fc1",
    "id": "arXiv Dataset",
    "type": "Model",
    "variant": "snapshot-2026-01-17",
    "version": "0.1.0"
  },
  "user_id": 1000002
}