{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreih5cft3aupntfx2fbe2t2gzektkfa3evvpw24uqmi4jzfmm55ndxm",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mg4u3jottfz2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.01282v1",
  "publishedAt": "2026-03-03T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Peyman Afshani",
    "Boris Aronov",
    "Kevin Buchin",
    "Maike Buchin",
    "Otfried Cheong",
    "Katharina Klost",
    "Carolin Rehs",
    "Günter Rote"
  ],
  "textContent": "**Authors:** Peyman Afshani, Boris Aronov, Kevin Buchin, Maike Buchin, Otfried Cheong, Katharina Klost, Carolin Rehs, Günter Rote\n\nLet $P$ and $Q$ be simple polygons with $n$ vertices each. We wish to compute triangulations of $P$ and $Q$ that are combinatorially equivalent, if they exist. We consider two versions of the problem: if a triangulation of $P$ is given, we can decide in $O(n\\log n + nr)$ time if $Q$ has a compatible triangulation, where $r$ is the number of reflex vertices of $Q$. If we are already given the correspondence between vertices of $P$ and $Q$ (but no triangulation), we can find compatible triangulations of $P$ and $Q$ in time $O(M(n))$, where $M(n)$ is the running time for multiplying two $n\\times n$ matrices.",
  "title": "Compatible Triangulations of Simple Polygons"
}