RETRACTED: 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 and 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 ray-shooting 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.