Dynamic 3D Convex Hulls Revisited and Applications

Chan [J. ACM, 2010] developed a data structure to maintain the convex hull of a dynamic set of points in 3D under insertions and deletions to answer certain queries on the convex hulls. The algorithm has been slightly improved by Kaplan, Mulzer, Roditty, Seiferth, and Sharir [Discret. Comput. Geom, 2020] and by Chan [Discret. Comput. Geom, 2020], without altering the main algorithmic framework. The current best result supports each insertion in O(log 2 n) amortized time, each deletion in O(log 4 n) amortized time, and each extreme query in O(log 2 n) worst-case time (along with other query types). These results have numerous applications, notably in dynamic Euclidean nearest neighbor searching in 2D. In the dual setting, the problem becomes maintaining the lower envelope of a dynamic set of 3D planes for vertical ray-shooting queries. By developing randomized vertical shallow cutting algorithms for general distance functions, Kaplan, Mulzer, Roditty, Seiferth, and Sharir [Discret. Comput. Geom, 2020] and Liu [SIAM J. Comput., 2022] extended Chan's framework to maintain the lower envelope of a dynamic set of general 3D surfaces. The best known result in this setting achieves O(log 2 n) amortized expected time for insertions, O(log 4 n) amortized expected time for deletions, and O(log 2 n) worst-case time for vertical rayshooting queries. As an immediate application, dynamic nearest neighbor searching under general distance functions (e.g., the L p metric or additively-weighted Euclidean distance) can be solved.

In this paper, we revisit Chan's algorithmic framework and propose a modified version that reduces the deletion time to O(log 3 n log log n), while retaining the O(log 2 n) insertion time at the cost of an increased query time of O(log 3 n/ log log n). Our result is particularly appealing in scenarios where the overall running time is dominated by the operation with the highest time complexity; in such cases, our approach offers an improvement of roughly a logarithmic factor over prior work based on Chan's original framework. This improvement translates into faster algorithms for several fundamental problems, including maintaining the dynamic 2D bichromatic closest pair, computing convex layers of 3D points, maintaining the minimum spanning tree of a dynamic 2D point set, and maintaining dynamic disk graph connectivity, among others.

In particular, we consider the problem of computing shortest paths in weighted disk graphs. The previous best algorithm, due to An, Oh, and Xue [SoCG 2025], runs in O(n log 4 n) time. We present a new algorithm that achieves an improved expected running time of O(n log 3 n log log n). Note that our algorithm is not merely the result of plugging our new dynamic data structure into the previous approach. Rather, we propose a different method, in which the new data structure plays a critical supporting role.