首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Efficient Algorithms for the Smallest Enclosing Ball Problem
Authors:Email author" target="_blank">Guanglu?ZhouEmail author  Kim-Chuan?Tohemail  Jie?Sun
Institution:(1) Department of Mathematics and Statistics, Curtin University of Technology, Bentley, WA, 6102, Australia;(2) Department of Mathematics, National University of Singapore, 2 Science Drive 2, Singapore, 117543;(3) Department of Decision Sciences, National University of Singapore, Singapore
Abstract:Consider the problem of computing the smallest enclosing ball of a set of m balls in realn. Existing algorithms are known to be inefficient when n > 30. In this paper we develop two algorithms that are particularly suitable for problems where n is large. The first algorithm is based on log-exponential aggregation of the maximum function and reduces the problem into an unconstrained convex program. The second algorithm is based on a second-order cone programming formulation, with special structures taken into consideration. Our computational experiments show that both methods are efficient for large problems, with the product mn on the order of 107. Using the first algorithm, we are able to solve problems with n = 100 and m = 512,000 in about 1 hour.His work was supported by Australian Research Council.Research supported in part by the Singapore-MIT Alliance.
Keywords:computational geometry  smoothing approximation  second order cone programming
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号