Compatible Triangulations of Simple Polygons
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908859196506112 |
|---|---|
| author | Afshani, Peyman Aronov, Boris Buchin, Kevin Buchin, Maike Cheong, Otfried Klost, Katharina Rehs, Carolin Rote, Günter |
| author_facet | Afshani, Peyman Aronov, Boris Buchin, Kevin Buchin, Maike Cheong, Otfried Klost, Katharina Rehs, Carolin Rote, Günter |
| contents | Let $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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_01282 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Compatible Triangulations of Simple Polygons Afshani, Peyman Aronov, Boris Buchin, Kevin Buchin, Maike Cheong, Otfried Klost, Katharina Rehs, Carolin Rote, Günter Computational Geometry Let $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 |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2603.01282 |