2024/12/13 by N. Moriya, Moriya, Netzer
Computer Science · Engineering · #Computational Geometry and Mesh Generation #Optimization and Packing Problems #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2412.10120
Efficient algorithms for solving the Smallest Enclosing Sphere (SES) problem,\nsuch as Welzl's algorithm, often fail to handle degenerate subsets of points in\n3D space. Degeneracies and ill-posed configurations present significant\nchallenges, leading to failures in convergence, inaccuracies or increased\ncomputational cost in such cases. Existing improvements to these algorithms,\nwhile addressing some of these issues, are either computationally expensive or\nonly partially effective. In this paper, we propose a hybrid algorithm designed\nto mitigate degeneracy while maintaining an overall computational complexity of\nO(N). By combining robust preprocessing steps with efficient core\ncomputations, our approach avoids the pitfalls of degeneracy without\nsacrificing scalability. The proposed method is validated through theoretical\nanalysis and experimental results, demonstrating its efficacy in addressing\ndegenerate configurations and achieving high efficiency in practice.\n