标题： 实用的仅插入凸包 显示英文标题

标题： Practical Insertion-Only Convex Hull

摘要： 凸包数据结构在计算几何中是基础性的。 我们研究仅插入的数据结构，支持各种包含和交集查询。 当$P$按$x$- 或$y$-坐标排序时，可以使用经典的算法如 Graham扫描在线性时间内构造凸包。 我们研究了针对仅插入设置的各种方法。 我们探讨了涉及鲁棒性、内存访问模式和空间使用的广泛权衡，提供了对现有和新方法的全面评估。 对数时间方法依赖于基于指针的树结构，由于内存局部性差，在实际中表现不佳。 受此启发，我们开发了一种受Overmars的对数方法启发的基于向量的解决方案。 我们的结构具有更差的渐近界，支持查询在$O(\log^2 n)$时间内完成，但将数据存储在$O(\log n)$连续向量中，大大提高了缓存性能。 通过在真实世界和合成数据集上的实证评估，我们发现了令人惊讶的趋势。 令$h$表示凸包的大小。 我们表明，基于Graham扫描的朴素$O(h)$仅插入算法在现实工作负载下始终优于理论和实际的最先进方法，即使在凸包相当大的数据集上也是如此。 虽然基于树的方法具有$O(\log h)$更新时间，提供了坚实的理论保证，但在实践中从不是最优的。 相反，我们的基于向量的对数方法，尽管其理论上的边界较差，但在所有测试场景中都表现出色。 当凸包变大时，它是最优的。 显示英文摘要

摘要： Convex hull data structures are fundamental in computational geometry. We study insertion-only data structures, supporting various containment and intersection queries. When $P$ is sorted by $x$- or $y$-coordinate, convex hulls can be constructed in linear time using classical algorithms such as Graham scan. We investigate a variety of methods tailored to the insertion-only setting. We explore a broad selection of trade-offs involving robustness, memory access patterns, and space usage, providing an extensive evaluation of both existing and novel techniques. Logarithmic-time methods rely on pointer-based tree structures, which suffer in practice due to poor memory locality. Motivated by this, we develop a vector-based solution inspired by Overmars' logarithmic method. Our structure has worse asymptotic bounds, supporting queries in $O(\log^2 n)$ time, but stores data in $O(\log n)$ contiguous vectors, greatly improving cache performance. Through empirical evaluation on real-world and synthetic data sets, we uncover surprising trends. Let $h$ denote the size of the convex hull. We show that a na\"ive $O(h)$ insertion-only algorithm based on Graham scan consistently outperforms both theoretical and practical state-of-the-art methods under realistic workloads, even on data sets with rather large convex hulls. While tree-based methods with $O(\log h)$ update times offer solid theoretical guarantees, they are never optimal in practice. In contrast, our vector-based logarithmic method, despite its theoretically inferior bounds, is highly competitive across all tested scenarios. It is optimal whenever the convex hull becomes large.