Computing Diverse and Nice Triangulations
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915335028867072 |
|---|---|
| author | Gálvez, Waldo Goswami, Mayank Merino, Arturo Park, GiBeom Tsai, Meng-Tsung |
| author_facet | Gálvez, Waldo Goswami, Mayank Merino, Arturo Park, GiBeom Tsai, Meng-Tsung |
| contents | We initiate the study of computing diverse triangulations to a given polygon. Given a simple $n$-gon $P$, an integer $ k \geq 2 $, a quality measure $σ$ on the set of triangulations of $P$ and a factor $ α\geq 1 $, we formulate the Diverse and Nice Triangulations (DNT) problem that asks to compute $k$ \emph{distinct} triangulations $T_1,\dots,T_k$ of $P$ such that a) their diversity, $\sum_{i < j} d(T_i,T_j) $, is as large as possible \emph{and} b) they are nice, i.e., $σ(T_i) \leq ασ^* $ for all $1\leq i \leq k$. Here, $d$ denotes the symmetric difference of edge sets of two triangulations, and $σ^*$ denotes the best quality of triangulations of $P$, e.g., the minimum Euclidean length.
As our main result, we provide a $\mathrm{poly}(n,k)$-time approximation algorithm for the DNT problem that returns a collection of $k$ distinct triangulations whose diversity is at least $1 - Θ(1/k)$ of the optimal, and each triangulation satisfies the quality constraint. This is accomplished by studying \emph{bi-criteria triangulations} (BCT), which are triangulations that simultaneously optimize two criteria, a topic of independent interest. We complement our approximation algorithms by showing that the DNT problem and the BCT problem are NP-hard.
Finally, for the version where diversity is defined as $\min_{i < j} d(T_i,T_j) $, we show a reduction from the problem of computing optimal Hamming codes, and provide an $n^{O(k)}$-time $\tfrac12$-approximation algorithm. This improves over the naive ${C_{n-2} \choose k} \approx 2^{O(nk)}$ time bound for enumerating all $k$-tuples among the triangulations of a simple $n$-gon, where $C_n$ denotes the $n$-th Catalan number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_01323 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computing Diverse and Nice Triangulations Gálvez, Waldo Goswami, Mayank Merino, Arturo Park, GiBeom Tsai, Meng-Tsung Computational Geometry Data Structures and Algorithms We initiate the study of computing diverse triangulations to a given polygon. Given a simple $n$-gon $P$, an integer $ k \geq 2 $, a quality measure $σ$ on the set of triangulations of $P$ and a factor $ α\geq 1 $, we formulate the Diverse and Nice Triangulations (DNT) problem that asks to compute $k$ \emph{distinct} triangulations $T_1,\dots,T_k$ of $P$ such that a) their diversity, $\sum_{i < j} d(T_i,T_j) $, is as large as possible \emph{and} b) they are nice, i.e., $σ(T_i) \leq ασ^* $ for all $1\leq i \leq k$. Here, $d$ denotes the symmetric difference of edge sets of two triangulations, and $σ^*$ denotes the best quality of triangulations of $P$, e.g., the minimum Euclidean length. As our main result, we provide a $\mathrm{poly}(n,k)$-time approximation algorithm for the DNT problem that returns a collection of $k$ distinct triangulations whose diversity is at least $1 - Θ(1/k)$ of the optimal, and each triangulation satisfies the quality constraint. This is accomplished by studying \emph{bi-criteria triangulations} (BCT), which are triangulations that simultaneously optimize two criteria, a topic of independent interest. We complement our approximation algorithms by showing that the DNT problem and the BCT problem are NP-hard. Finally, for the version where diversity is defined as $\min_{i < j} d(T_i,T_j) $, we show a reduction from the problem of computing optimal Hamming codes, and provide an $n^{O(k)}$-time $\tfrac12$-approximation algorithm. This improves over the naive ${C_{n-2} \choose k} \approx 2^{O(nk)}$ time bound for enumerating all $k$-tuples among the triangulations of a simple $n$-gon, where $C_n$ denotes the $n$-th Catalan number. |
| title | Computing Diverse and Nice Triangulations |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.01323 |