Evaluating Cooling Center Coverage Using Persistent Homology of a Filtered Witness Complex
该论文利用持久同调和见证复形方法评估冷却中心覆盖中的地理缺口，并通过在四个城市将其与热脆弱性指数进行对比，揭示了从拓扑和人口统计双重视角识别热相关死亡风险区域的互补价值。
💻 Category
cs.CG
37 篇论文
Stochastic and incremental subgradient methods for convex optimization on Hadamard spaces
该论文针对非正曲率度量空间（Hadamard 空间）中缺乏线性结构导致次梯度构造困难的问题，提出了一种基于 Busemann 函数的新型次梯度定义，并据此构建了具有复杂度保证的随机及增量次梯度优化算法，成功应用于 BHV 树空间等场景下的 -均值问题求解。
On the Diameter of Arrangements of Topological Disks
本文证明了由 个拓扑圆盘构成的排列的对偶图直径可由 和圆盘两两交集连通分量数的最大值 界定，具体给出了两圆盘情形下的紧确界以及 个圆盘情形下的 上界，并揭示了最大面数量的相关界限。
Computing Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness
该论文通过细粒度复杂性分析，揭示了在计算平移下的 豪斯多夫距离时，维度、对称性（有向与无向）及离散性（连续与离散）之间复杂的相互作用，并针对连续有向情形提出了不对称的时间复杂度结果、证明了 时有向与无向变体的条件性分离，以及指出了离散情形在 时归约至 3SUM 问题从而限制了基于正交向量假设的下界证明。
The Spanning Ratio of the Directed -Graph is 5
该论文首次证明了定向图的跨度比紧确界为 5，从而解决了此前该值介于 4 到 7 之间的未决问题。
Simultaneous Embedding of Two Paths on the Grid
该论文研究了网格上两条路径的无自交同时几何嵌入问题，证明了最小化最长边长度是 NP 难的，并提出了当一条路径为 x 单调、另一条为 y 单调时，可在 时间内最小化包含该嵌入的整数网格周长的算法。
Prismatoid Band-Unfolding Revisited
本文通过刻画嵌套棱锥体带展开不重叠的充要条件，证明了此前已知的反例在某种意义上是唯一的反例，从而深化了对棱锥体边展开问题的理解并为解决非嵌套情形提供了新工具。
Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree
该论文提出了一种基于新型混合双曲四叉树分解和加权交叉分析的随机移位分层动态规划算法，在 Gap-ETH 假设下为维双曲空间中的旅行商问题和斯坦纳树问题构建了具有最优依赖关系的-近似方案。
Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
该论文将低维欧几里得空间中-中值和-均值问题的-近似算法运行时间从$2^{(1/\varepsilon)^{O(d^2)}}n2^{\tilde{O}(1/\varepsilon)^{d-1}}nd-1$的下界，从而确立了近乎紧致的复杂度界限。
Invariants of almost embeddings of graphs in the plane
本文面向非拓扑学背景读者，研究了平面中图几乎嵌入的不变量，揭示了其与图删除积同调之间的联系，构造了实现特定不变量值的几乎嵌入，并提出了相关猜想与开放问题。
Topological Spatial Graph Coarsening
本文提出了一种基于三角形感知图滤过和持久图描述符的参数化空间图粗化方法，通过折叠短边在显著减小图规模的同时，有效保留了原始空间图的关键拓扑特征，并具备旋转、平移及缩放不变性。
Efficient Neighbourhood Search in 3D Point Clouds Through Space-Filling Curves and Linear Octrees
该论文提出了一种结合空间填充曲线（Morton 和 Hilbert 曲线）重排序与线性八叉树的高效 3D 点云邻域搜索方法，通过引入 kNN 局部性直方图优化缓存访问，实现了比现有方案快 10 倍的搜索速度及高达 36 倍的并行加速比。
Geometry and design of popup structures
本文通过建立基于折纸与剪纸几何的弹出式结构离散曲面曲率定义，提出了一种能够根据预设形状设计折切图案并实现单一结构在展开过程中从负曲率向正曲率转变的设计流程，并展示了其在减阻、包装及建筑立面等领域的应用潜力。
Which Vertical Graphs are Non VPHT Reconstructible?
本文研究了顶点共线的垂直图在何种情况下无法通过 verbose 持久同调变换（VPHT）重构，并确定了此类图不可重构的必要条件与充分条件。
The Li-Chao Tree: Algorithm Specification and Analysis
本文首次为在竞赛编程中广泛使用但缺乏正式文献记载的李超树提供了包含完整算法规范、正确性证明、复杂度分析及实证性能评估的权威形式化定义。
Geometric Give and Take
该论文研究了由 Spencer 提出的几何平衡博弈的一个特例，确定了在 条直线构成的平面排列中，Alice 能够阻止 Bob 获胜所需的最小初始石子数 ，证明了该数值可在多项式时间内计算，且对于一般位置的直线排列，其量级为 。
Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
该论文研究了排列匹配拼图问题，完全刻画了基于行列升降约束的网格填数谜题的可解性条件（即约束图无环或标签切换不超过一次），给出了可解情况下的解数钩长公式及不可解情况下的最小修复算法，并证明了当约束推广为任意排列时，寻找最小修复方案是 NP 完全的。
Topologically Stable Hough Transform
该论文提出了一种基于持续同态的拓扑稳定霍夫变换新框架，通过用连续评分函数替代传统的离散投票机制，从点云中高效检测出候选直线。
The Complexity of Extending Storylines with Minimum Local Crossing Number
该论文研究了在固定子故事线布局下插入缺失角色以最小化局部交叉数的扩展问题，并证明了该问题在参数下是W[1]-难的，在参数下属于XP类，而在参数下是固定参数可解的。
Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs
本文针对圆盘图的最大团问题，提出了两种随机化近似算法：一种针对单位圆盘图实现了期望时间的-近似，另一种针对具有种不同半径的圆盘图实现了参数化近似方案，其期望运行时间为。