跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+1292新增论文
+1016其中 AI 相关
+166已有论文修订
+59新增 AI 导读

arXiv 最近完成扫描:2026-11-18 04:28 · 全站最近入库:2026-11-18 11:33各信源进度 →

统计口径与数据新鲜度

统计 2026-11-17 12:30 — 2026-11-18 12:30(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-18 04:28最近发现新增版本:2026-11-18 11:33库内论文最新更新时间:2026-11-17 20:55

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

25,964 已收录论文21,631 AI 相关7,801 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 1 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-18 04:27(北京时间)
版本更新 · v3arXiv:2605.21921

凸多边形的加权部分三角剖分

On weighted partial triangulations of convex polygons

Antonio Blanca, Alexandre Stauffer, Izabella Stuhl

AI 速读 基于摘要

研究凸多边形加权部分三角剖分的精确采样问题,并给出期望运行时间接近最优的采样算法。

cs.DM · math.CO

查看原文摘要

We study the problem of sampling weighted partial triangulations of a convex polygon with $n+2$ sides. We consider the distribution $π_{n,λ}$ under which each partial triangulation $σ$ is assigned probability proportional to $λ^{|σ|}$, where $λ>0$ is a model parameter and $|σ| \in \{0,\dots,n-1\}$ denotes the number of diagonals in $σ$. This model belongs to a broad class of weighted geometric partition problems that include lattice triangulations and dyadic tilings, and is closely related to several classical combinatorial structures, including the full triangulations of a convex polygon and the associated Catalan structures. Our main result is a simple exact sampling algorithm for $π_{n,λ}$ with expected running time $O\big((\min\{n,n\sqrtλ\}+1)\log n\big)$, which is optimal up to the logarithmic factor.