{
  "annotation_id": "8fc45555-1568-4ec2-be5c-6d73ae8c2263",
  "date_created": "2026-02-17T05:53:16.238000Z",
  "date_modified": "2026-02-17T05:53:16.238000Z",
  "file_hash": "a9466585ff583d6be81333271c9bfa4f75f265a1aad28547402d54415f639569",
  "private": false,
  "record": {
    "abstract": "We investigate algorithms with predictions in computational geometry, specifically focusing on the basic problem of computing 2D Delaunay triangulations. Given a set $P$ of $n$ points in the plane and a triangulation $G$ that serves as a \"prediction\" of the Delaunay triangulation, we would like to use $G$ to compute the correct Delaunay triangulation $\\textit{DT}(P)$ more quickly when $G$ is \"close\" to $\\textit{DT}(P)$. We obtain a variety of results of this type, under different deterministic and probabilistic settings, including the following: 1. Define $D$ to be the number of edges in $G$ that are not in $\\textit{DT}(P)$. We present a deterministic algorithm to compute $\\textit{DT}(P)$ from $G$ in $O(n + D\\log^3 n)$ time, and a randomized algorithm in $O(n+D\\log n)$ expected time, the latter of which is optimal in terms of $D$. 2. Let $R$ be a random subset of the edges of $\\textit{DT}(P)$, where each edge is chosen independently with probability $\\rho$. Suppose $G$ is any triangulation of $P$ that contains $R$. We present an algorithm to compute $\\textit{DT}(P)$ from $G$ in $O(n\\log\\log n + n\\log(1/\\rho))$ time with high probability. 3. Define $d_{\\mbox{\\scriptsize\\rm vio}}$ to be the maximum number of points of $P$ strictly inside the circumcircle of a triangle in $G$ (the number is 0 if $G$ is equal to $\\textit{DT}(P)$). We present a deterministic algorithm to compute $\\textit{DT}(P)$ from $G$ in $O(n\\log^*n + n\\log d_{\\mbox{\\scriptsize\\rm vio}})$ time. We also obtain results in similar settings for related problems such as 2D Euclidean minimum spanning trees, and hope that our work will open up a fruitful line of future research.",
    "arxiv_id": "2601.08106",
    "authors": [
      "Sergio Cabello",
      "Timothy M. Chan",
      "Panos Giannopoulos"
    ],
    "categories": [
      "cs.CG",
      "cs.DS"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "title": "Delaunay Triangulations with Predictions",
    "url": "https://arxiv.org/abs/2601.08106",
    "version": "v1"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "0fff3ac3-6348-4a63-a1c9-c934a84ee38a",
    "id": "arXiv Dataset",
    "type": "Model",
    "variant": "snapshot-2026-01-17",
    "version": "0.1.0"
  },
  "user_id": 1000002
}