计算几何

2025年04月 的作者和标题

[1] arXiv:2504.00067 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 匹配随机着色点的矩形(更正) 显示英文标题

标题： Matching random colored points with rectangles (Corrigendum)

Josué Corujo, Paul Horn, Pablo Pérez-Lantero

主题： 计算几何 (cs.CG)

[2] arXiv:2504.02334 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 通过成对距离确定球体半径 显示英文标题

标题： Determining Sphere Radius through Pairwise Distances

Boris Sukhovilov

评论： 10页，我们将方法的实现作为开源代码发布在https://github.com/boris-sukhovilov/Sphere_Radius

主题： 计算几何 (cs.CG) ; 计算机视觉与模式识别 (cs.CV)

[3] arXiv:2504.02611 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 实例最优的模糊凸包 显示英文标题

标题： Instance-Optimal Imprecise Convex Hull

Sarita de Berg, Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann, Sampson Wong

主题： 计算几何 (cs.CG)

[4] arXiv:2504.02650 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 利用SAT研究$K_n$的简单绘图 显示英文标题

标题： Investigating Simple Drawings of $K_n$ using SAT

Helena Bergold, Manfred Scheucher

评论： arXiv管理员注：文本与arXiv:2305.09432存在重叠。

主题： 计算几何 (cs.CG) ; 离散数学 (cs.DM) ; 组合数学 (math.CO)

[5] arXiv:2504.03558 (交叉列表自 cs.CG) [中文pdf, pdf, 其他]

标题： 寻找一条将少数对象与多数对象分开的最短曲线 显示英文标题

标题： Finding a Shortest Curve that Separates Few Objects from Many

Therese Biedl, Éric Colin de Verdière, Fabrizio Frati, Anna Lubiw, Günter Rote

评论： 45页，19幅图，13个附录。本文将不包含附录的形式出现在第41届国际计算几何研讨会（SoCG 2025）日本金泽的会议录中；由Oswin Aichholzer和Haitao Wang编辑；Leibniz国际信息学讲座论文集（LIPIcs），第332卷，文章编号15。

主题： 计算几何 (cs.CG)

[6] arXiv:2504.03610 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 使用强化学习优化三角Delaunay网格生成器 显示英文标题

标题： Optimization of a Triangular Delaunay Mesh Generator using Reinforcement Learning

Will Thacher, Per-Olof Persson, Yulong Pan

主题： 计算几何 (cs.CG)

[7] arXiv:2504.03865 (交叉列表自 cs.CG) [中文pdf, pdf, 其他]

标题： 面向Mapper图上交错距离的最优界 显示英文标题

标题： Towards an Optimal Bound for the Interleaving Distance on Mapper Graphs

Erin Wolf Chambers, Ishika Ghosh, Elizabeth Munch, Sarah Percival, Bei Wang

评论： 修正定义2.5中的拼写错误；添加了一个实验

主题： 计算几何 (cs.CG)

[8] arXiv:2504.04412 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 最小非钝角三角剖分：CG:SHOP挑战赛2025 显示英文标题

标题： Minimum Non-Obtuse Triangulations: The CG:SHOP Challenge 2025

Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, Stefan Schirra

评论： 11页，3幅图

主题： 计算几何 (cs.CG) ; 数据结构与算法 (cs.DS)

[9] arXiv:2504.05098 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 球面上的壳图和沉没图 显示英文标题

标题： Shelling and Sinking Graphs on the Sphere

Jeff Erickson, Christian Howard

评论： 28页，12幅图。SOCG 2025即将发表的论文完整版本。

主题： 计算几何 (cs.CG)

[10] arXiv:2504.05861 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 几何交集图的稀疏有界跳数跨度图 显示英文标题

标题： Sparse Bounded Hop-Spanners for Geometric Intersection Graphs

Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang, Shakhar Smorodinsky, Csaba D. Toth

评论： 21页。本文的扩展摘要将出现在2025年SoCG会议 proceedings 中。

主题： 计算几何 (cs.CG) ; 离散数学 (cs.DM)

[11] arXiv:2504.06079 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 基于几何二分匹配的服务器问题精确算法 显示英文标题

标题： Geometric Bipartite Matching Based Exact Algorithms for Server Problems

Sharath Raghvendra, Pouyan Shirzadian, Rachita Sowle

主题： 计算几何 (cs.CG)

[12] arXiv:2504.06376 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 量子组合与征服及其在次线性量子凸包和最大集构造中的应用 显示英文标题

标题： Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction

Shion Fukuzawa, Michael T. Goodrich, Sandy Irani

评论： 17页，7个图，即将发表在SoCG2025上

主题： 计算几何 (cs.CG) ; 量子物理 (quant-ph)

[13] arXiv:2504.06503 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 将图嵌入为欧几里得kNN图 显示英文标题

标题： Embedding Graphs as Euclidean kNN-Graphs

T. Schibler, S. Suri, J. Xue

评论： 将于2025年出现在SoCG上

主题： 计算几何 (cs.CG)

[14] arXiv:2504.06960 (交叉列表自 cs.CG) [中文pdf, pdf, 其他]

标题： 高阶彩色Voronoi图与彩色Clarkson-Shor框架 显示英文标题

标题： Higher-Order Color Voronoi Diagrams and the Colorful Clarkson-Shor Framework

Sang Won Bae, Nicolau Oliver, Evanthia Papadopoulou

评论： 43页，11幅图

主题： 计算几何 (cs.CG)

[15] arXiv:2504.07545 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 凸性有助于三维中的迭代搜索 显示英文标题

标题： Convexity Helps Iterated Search in 3D

Peyman Afshani, Yakov Nekrich, Frank Staals

评论： 我们即将在SoCG 2025上发表的完整版论文

主题： 计算几何 (cs.CG)

[16] arXiv:2504.08847 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 受肥皂膜启发的细分晶格结构构造 显示英文标题

标题： Soap Film-inspired Subdivisional Lattice Structure Construction

Guoyue Luo, Qiang Zou

主题： 计算几何 (cs.CG) ; 图形学 (cs.GR)

[17] arXiv:2504.09174 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 交换代数增强的拓扑数据分析 显示英文标题

标题： Commutative algebra-enhanced topological data analysis

Chuanshen Hu, Yu Wang, Kelin Xia, Ke Ye, Yipeng Zhang

主题： 计算几何 (cs.CG) ; 交换代数 (math.AC) ; 代数拓扑 (math.AT)

[18] arXiv:2504.09489 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 方形单位包装具有渐进最小浪费，只需要好的方块 显示英文标题

标题： Square Packing with Asymptotically Smallest Waste Only Needs Good Squares

Hong Duc Bui

评论： 7页，7幅图，提交至CCCG 2025

主题： 计算几何 (cs.CG)

[19] arXiv:2504.09615 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 点集三角剖分的数量计算：重新解释与推广三角剖分多项式 显示英文标题

标题： Counting Number of Triangulations of Point Sets: Reinterpreting and Generalizing the Triangulation Polynomials

Hong Duc Bui

评论： 14页，8幅图

主题： 计算几何 (cs.CG)

[20] arXiv:2504.09733 (交叉列表自 cs.CG) [中文pdf, pdf, 其他]

标题： 二维黑盒分类器函数的基于ε-邻域决策边界的估计（EDGE） 显示英文标题

标题： Epsilon-Neighborhood Decision-Boundary Governed Estimation (EDGE) of 2D Black Box Classifier Functions

Mithun Goutham, Riccardo DalferroNucci, Stephanie Stockar, Meghna Menon, Sneha Nayak, Harshad Zade, Chetan Patel, Mario Santillo

主题： 计算几何 (cs.CG) ; 机器学习 (cs.LG) ; 数值分析 (math.NA)

[21] arXiv:2504.10657 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 平衡TSP划分 显示英文标题

标题： Balanced TSP partitioning

Benjamin Aram Berendsohn, Hwi Kim, László Kozma

主题： 计算几何 (cs.CG) ; 数据结构与算法 (cs.DS)

[22] arXiv:2504.10859 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 一种用于矩形障碍物路径可行性的次线性算法 显示英文标题

标题： A Sublinear Algorithm for Path Feasibility Among Rectangular Obstacles

Alex Fan, Alicia Li, Arul Kolla, Jason Gonzalez

主题： 计算几何 (cs.CG) ; 机器人技术 (cs.RO)

[23] arXiv:2504.11203 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 编织葡萄园 显示英文标题

标题： Braiding vineyards

Erin Chambers, Christopher Fillmore, Elizabeth Stephenson, Mathijs Wintraecken

评论： 27页，15幅图

主题： 计算几何 (cs.CG) ; 代数拓扑 (math.AT) ; 几何拓扑 (math.GT)

[24] arXiv:2504.12022 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 离散打包与 domination 的硬度和近似方案 显示英文标题

标题： Hardness and Approximation Schemes for Discrete Packing and Domination

Raghunath Reddy Madireddy, Apurva Mudgal, Supantha Pandit

主题： 计算几何 (cs.CG)

[25] arXiv:2504.12948 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 用于$2$维格子的最短向量问题的算法，重新审视 显示英文标题

标题： Algorithms for the Shortest Vector Problem in $2$-dimensional Lattices, Revisited

Lihao Zhao, Chengliang Tian, Jingguo Bi, Guangwu Xu, Jia Yu

主题： 计算几何 (cs.CG) ; 密码学与安全 (cs.CR)

[26] arXiv:2504.13704 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 一个接近线性时间的精确算法，用于简单多边形边界上两条曲线之间的$L_1$-地真 Fréchet 距离 显示英文标题

标题： A near-linear time exact algorithm for the $L_1$-geodesic Fréchet distance between two curves on the boundary of a simple polygon

Thijs van der Horst, Marc van Kreveld, Tim Ophelders, Bettina Speckmann

评论： 19页，5幅图

主题： 计算几何 (cs.CG)

[27] arXiv:2504.14743 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 中轴变换的中球表亲 显示英文标题

标题： The Mid-sphere Cousin of the Medial Axis Transform

Herbert Edelsbrunner, Elizabeth Stephenson, Martin Hafskjold Thoresen

主题： 计算几何 (cs.CG) ; 代数拓扑 (math.AT)

[28] arXiv:2504.15292 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 几何问题的区间计数查询器 显示英文标题

标题： Range Counting Oracles for Geometric Problems

Anne Driemel, Morteza Monemizadeh, Eunjin Oh, Frank Staals, David P. Woodruff

评论： 已被SoCG'25接受

主题： 计算几何 (cs.CG) ; 数据结构与算法 (cs.DS)

[29] arXiv:2504.16642 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 打击和覆盖仿射凸多面体族，及其在鲁棒优化中的应用 显示英文标题

标题： Hitting and Covering Affine Families of Convex Polyhedra, with Applications to Robust Optimization

Jean Cardinal, Xavier Goaoc, Sarah Wajsbrot

评论： 18页，2幅图

主题： 计算几何 (cs.CG) ; 优化与控制 (math.OC)

[30] arXiv:2504.16762 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 多米诺骨牌在各种全局控制模型中的可排空性和可填充性 显示英文标题

标题： Drainability and Fillability of Polyominoes in Diverse Models of Global Control

Sándor P. Fekete, Peter Kramer, Jan-Marc Reinhardt, Christian Rieck, Christian Scheffer

评论： 24页，17幅图，将发表于第52届EATCS国际自动机、语言和编程会议（ICALP 2025）论文集。

主题： 计算几何 (cs.CG)

[31] arXiv:2504.17289 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 平面上用障碍物分离两点：改进的上下界 显示英文标题

标题： Separating Two Points with Obstacles in the Plane: Improved Upper and Lower Bounds

Jack Spalding-Jamieson, Anurag Murty Naredla

评论： 32页，16图

主题： 计算几何 (cs.CG)

[32] arXiv:2504.17342 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 无权平面图中的弗雷歇距离 显示英文标题

标题： Fréchet Distance in Unweighted Planar Graphs

Ivor van der Hoog, Thijs van der Horst, Eva Rotenberg, Lasse Wulf

评论： 参加2025年ESA

主题： 计算几何 (cs.CG)

[33] arXiv:2504.17381 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 三次时间内的子轨迹聚类与覆盖最大化，或更优 显示英文标题

标题： Subtrajectory Clustering and Coverage Maximization in Cubic Time, or Better

Jacobus Conradi, Anne Driemel

主题： 计算几何 (cs.CG)

[34] arXiv:2504.17955 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 马可波罗问题：一种组合方法的几何定位 显示英文标题

标题： The Marco Polo Problem: A Combinatorial Approach to Geometric Localization

Ofek Gila (1), Michael T. Goodrich (1), Zahra Hadizadeh (2), Daniel S. Hirschberg (1), Shayan Taherijam (1) ((1) University of California, Irvine, (2) University of Rochester)

评论： 11页，15幅图，1张表

主题： 计算几何 (cs.CG) ; 数据结构与算法 (cs.DS)

[35] arXiv:2504.18178 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 最小相交和最小包含球 显示英文标题

标题： Smallest Intersecting and Enclosing Balls

Jiaqi Zheng, Tiow-Seng Tan

评论： 计算几何：青年研究论坛（CG:YRF），2025

主题： 计算几何 (cs.CG)

[36] arXiv:2504.18352 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 线性时间算法求解两个凸多边形在平移下的最大重叠区域 显示英文标题

标题： A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation

Timothy M. Chan, Isaac M. Hair

评论： 将出现在SoCG 2025

主题： 计算几何 (cs.CG)

[37] arXiv:2504.21329 (交叉列表自 cs.CG) [中文pdf, pdf, html, 其他]

标题： 绘制Reeb图 显示英文标题

标题： Drawing Reeb Graphs

Erin Chambers, Brittany Terese Fasy, Erfan Hosseini Sereshgi, Maarten Löffler

评论： 这项工作的初步摘要曾作为海报在GD 2023上展示，简短版本已被IWOCA 2025接受。

主题： 计算几何 (cs.CG)

[38] arXiv:2504.00032 (交叉列表自 cs.CV) [中文pdf, pdf, html, 其他]

标题： 骨架化质量评估：机器人点云分析中的几何度量 显示英文标题

标题： Skeletonization Quality Evaluation: Geometric Metrics for Point Cloud Analysis in Robotics

Qingmeng Wen, Yu-Kun Lai, Ze Ji, Seyed Amir Tafrishi

评论： 15页，12幅图，正在审稿中

主题： 计算机视觉与模式识别 (cs.CV) ; 计算几何 (cs.CG) ; 机器人技术 (cs.RO)

[39] arXiv:2504.00292 (交叉列表自 cs.RO) [中文pdf, pdf, html, 其他]

标题： 移动部件的顺应性和避碰协同优化设计 显示英文标题

标题： Co-design Optimization of Moving Parts for Compliance and Collision Avoidance

Amir M. Mirzendehdel, Morad Behandish

期刊参考： 计算机辅助设计 (2023)

主题： 机器人技术 (cs.RO) ; 计算几何 (cs.CG)

[40] arXiv:2504.00916 (交叉列表自 math.GT) [中文pdf, pdf, html, 其他]

标题： 曲面上曲线的交叉数不等式 显示英文标题

标题： Crossing number inequalities for curves on surfaces

Alfredo Hubard, Hugo Parlier

评论： 18页，6个图

主题： 几何拓扑 (math.GT) ; 计算几何 (cs.CG) ; 组合数学 (math.CO)

[41] arXiv:2504.00932 (交叉列表自 math.CO) [中文pdf, pdf, 其他]

标题： 强子线性分隔符和有界渐近维度的球面交集图 显示英文标题

标题： Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs

James Davies, Agelos Georgakopoulos, Meike Hatzel, Rose McCarty

评论： 20页，2幅图

主题： 组合数学 (math.CO) ; 计算几何 (cs.CG) ; 离散数学 (cs.DM) ; 度量几何 (math.MG)

[42] arXiv:2504.01113 (交叉列表自 math.ST) [中文pdf, pdf, html, 其他]

标题： 多参数持久性景观的置信带 显示英文标题

标题： Confidence Bands for Multiparameter Persistence Landscapes

Inés García-Redondo, Anthea Monod, Qiquan Wang

评论： 11页，1个图

主题： 统计理论 (math.ST) ; 计算几何 (cs.CG) ; 代数拓扑 (math.AT)

[43] arXiv:2504.02190 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 一个关于具有相似长度的平行线段簇上的旅行商问题的PTAS（多项式时间近似方案） 显示英文标题

标题： A PTAS for Travelling Salesman Problem with Neighbourhoods Over Parallel Line Segments of Similar Length

Benyamin Ghaseminia, Mohammad R. Salavatipour

评论： 将于SoCG 2025 proceedings中发表的扩展摘要

主题： 数据结构与算法 (cs.DS) ; 计算几何 (cs.CG)

[44] arXiv:2504.03942 (交叉列表自 math.GT) [中文pdf, pdf, html, 其他]

标题： 一个实用的纽结分解算法 显示英文标题

标题： A Practical Algorithm for Knot Factorisation

Alexander He, Eric Sedgwick, Jonathan Spreer

评论： 36页，14幅图。SoCG 2025会议的简短版本将会发表；此完整版包含了简版中省略的细节。

主题： 几何拓扑 (math.GT) ; 计算几何 (cs.CG)

[45] arXiv:2504.04361 (交叉列表自 math.AT) [中文pdf, pdf, html, 其他]

标题： 关于持久性图之间的余弦相似性和正交性 显示英文标题

标题： On the cosine similarity and orthogonality between persistence diagrams

Azmeer Nordin, Mohd Salmi Md Noorani, Nurulkamal Masseran, Mohd Sabri Ismail, Nur Firyal Roslan

评论： 25页，4幅图

主题： 代数拓扑 (math.AT) ; 计算几何 (cs.CG)

[46] arXiv:2504.04594 (交叉列表自 math.MG) [中文pdf, pdf, 其他]

标题： 线与条带之间的不同距离 显示英文标题

标题： Distinct Distances Between a Line and Strip

Sanjana Das, Adam Sheffer

主题： 度量几何 (math.MG) ; 计算几何 (cs.CG) ; 组合数学 (math.CO)

[47] arXiv:2504.05921 (交叉列表自 cs.RO) [中文pdf, pdf, 其他]

标题： 移动机器人路径规划的加速Reeds-Shepp和欠指定Reeds-Shepp算法 显示英文标题

标题： Accelerated Reeds-Shepp and Under-Specified Reeds-Shepp Algorithms for Mobile Robot Path Planning

Ibrahim Ibrahim, Wilm Decré, Jan Swevers

评论： 19页，27幅图

期刊参考： 《IEEE机器人学汇刊》，2025年3月24日

主题： 机器人技术 (cs.RO) ; 计算几何 (cs.CG)

[48] arXiv:2504.06434 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 单位圆图中反向最短路径的快速算法及其相关几何优化问题：改进收缩与分支技术 显示英文标题

标题： Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique

Timothy M. Chan, Zhengcheng Huang

主题： 数据结构与算法 (cs.DS) ; 计算几何 (cs.CG)

[49] arXiv:2504.06534 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： 带权圆盘图中的单源最短路径问题 显示英文标题

标题： Single-Source Shortest Path Problem in Weighted Disk Graphs

Shinwoo An, Eunjin Oh, Jie Xue

评论： 在SoCG'25上

主题： 数据结构与算法 (cs.DS) ; 计算几何 (cs.CG)

[50] arXiv:2504.07322 (交叉列表自 cs.LG) [中文pdf, pdf, html, 其他]

标题： Bregman-Hausdorff散度：加强计算几何与机器学习之间的联系 显示英文标题

标题： Bregman-Hausdorff divergence: strengthening the connections between computational geometry and machine learning

Tuyen Pham, Hana Dal Poz Kouřimská, Hubert Wagner

评论： 23页，11幅图，3张表格，3个算法，投稿至《机器学习与知识提取》

主题： 机器学习 (cs.LG) ; 计算几何 (cs.CG) ; 信息论 (cs.IT)