• Previous Article
    Asymptotics for ruin probabilities of a non-standard renewal risk model with dependence structures and exponential Lévy process investment returns
  • JIMO Home
  • This Issue
  • Next Article
    $ (Q,r) $ Model with $ CVaR_α $ of costs minimization
January  2017, 13(1): 147-153. doi: 10.3934/jimo.2016009

An efficient cutting plane algorithm for the smallest enclosing circle problem

1. 

VC/VR Lab and Department of Mathematics, Sichuan Normal University, Chengdu, Sichuan 610066, China

2. 

Department of Mathematics, Sichuan Normal University, Chengdu, Sichuan 610066, China

3. 

Neijiang Vocational Technical College, Neijiang, Sichuan 641100, China

* Corresponding author

Received  April 2015 Revised  December 2015 Published  March 2016

Fund Project: The first author is supported by National Natural Science Foundation of China No.11126336 and No.11201324, New Teachers’ Fund for Doctor Stations, Ministry of Education No.20115134120001, Fok Ying Tuny Education Foundation No.141114, Youth fund of Sichuan province No.2013JQ0027.

In this paper, we consider the problem of computing the smallest enclosing circle. An efficient cutting plane algorithm is derived. It is based on finding the valid cut and reducing the problem into solving a series of linear programs. The numerical performance of this algorithm outperforms other existing algorithms in our computational experiments.

Citation: Yi Jiang, Chuan Luo, Shenggui Ling. An efficient cutting plane algorithm for the smallest enclosing circle problem. Journal of Industrial & Management Optimization, 2017, 13 (1) : 147-153. doi: 10.3934/jimo.2016009
References:
[1]

M. Berg, Computational Geometry: Algorithms and Applicaions, Springer, New York, 1997. doi: 10.1007/978-3-662-03427-9.  Google Scholar

[2]

P. Chrystal, On the problem to construct the minimum circle enclosing n given points in a plan, in Proceedings of the Edinburgh Mathematical Society, Tird Meeting, 1885, 30. Google Scholar

[3]

J. Eliosoff and R. Unger, Minimal spanning circle of a set of points, Computer Science: Computational Geometry Project, School of Computer Science, McGill University, 1998,308– 507. Google Scholar

[4]

J. Elzinga and D. Hearn, The minimum covering sphere problem, Management Sci., 19 (1972), 96-104.  doi: 10.1287/mnsc.19.1.96.  Google Scholar

[5]

B. Gärtner, Fast and robust smallest enclosing balls, in Algorithms-ESA' 99: 7th Annual European Symposium, Proceedings (eds. J. Nestril), Lecture Notes in Computer Science, 1643, Springer-Verlag, 1999,325–338. Google Scholar

[6]

D. W. Hearn and J. Vijan, Efficient algorithms for the minimum circle problem, Oper. Res., 30 (1982), 777-795.  doi: 10.1287/opre.30.4.777.  Google Scholar

[7]

M. LoboL. VandenbergheS. Boyd and H. Lebret, Applications of second-order cone programming, Linear Albebra and its Applications, 284 (1998), 193-228.  doi: 10.1016/S0024-3795(98)10032-0.  Google Scholar

[8]

J. Sturm, Using SeDuMi 1. 02, a MATLAB toolbox for optimization over symmetric cones Optim. Methods Softw., 11/12 (1999), 625-653. doi: 10.1080/10556789908805766.  Google Scholar

[9]

Y. TianS. C. FangZ. B. Deng and W. X. Xing, Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming, Journal of Industrial and Management Optimization, 9 (2013), 703-721.  doi: 10.3934/jimo.2013.9.703.  Google Scholar

[10]

S. Y. WangY. J. Liu and Y. Jiang, A majorized penalty approach to inverse linear second order cone programming problems, Journal of Industrial and Management Optimization, 10 (2014), 965-976.  doi: 10.3934/jimo.2014.10.965.  Google Scholar

[11]

E. Welzl, Smalleat enclosing disks (balls and ellipsoids), in New Results and New Trends in Computer Science, Springer-Verlag, 1991,359–370. doi: 10.1007/BFb0038202.  Google Scholar

[12]

S. XuR. Freund and J. Sun, Solution methodologies for the smallest enclosing circle problem, Comput. Optim. Appl., 25 (2003), 283-292.  doi: 10.1023/A:1022977709811.  Google Scholar

[13]

Y. ZhangY. JiangL. Zhang and J. Zhang, A perturbation approach for an inverse linear second-order cone programming, Journal of Industrial and Management Optimization, 9 (2013), 171-189.  doi: 10.3934/jimo.2013.9.171.  Google Scholar

show all references

References:
[1]

M. Berg, Computational Geometry: Algorithms and Applicaions, Springer, New York, 1997. doi: 10.1007/978-3-662-03427-9.  Google Scholar

[2]

P. Chrystal, On the problem to construct the minimum circle enclosing n given points in a plan, in Proceedings of the Edinburgh Mathematical Society, Tird Meeting, 1885, 30. Google Scholar

[3]

J. Eliosoff and R. Unger, Minimal spanning circle of a set of points, Computer Science: Computational Geometry Project, School of Computer Science, McGill University, 1998,308– 507. Google Scholar

[4]

J. Elzinga and D. Hearn, The minimum covering sphere problem, Management Sci., 19 (1972), 96-104.  doi: 10.1287/mnsc.19.1.96.  Google Scholar

[5]

B. Gärtner, Fast and robust smallest enclosing balls, in Algorithms-ESA' 99: 7th Annual European Symposium, Proceedings (eds. J. Nestril), Lecture Notes in Computer Science, 1643, Springer-Verlag, 1999,325–338. Google Scholar

[6]

D. W. Hearn and J. Vijan, Efficient algorithms for the minimum circle problem, Oper. Res., 30 (1982), 777-795.  doi: 10.1287/opre.30.4.777.  Google Scholar

[7]

M. LoboL. VandenbergheS. Boyd and H. Lebret, Applications of second-order cone programming, Linear Albebra and its Applications, 284 (1998), 193-228.  doi: 10.1016/S0024-3795(98)10032-0.  Google Scholar

[8]

J. Sturm, Using SeDuMi 1. 02, a MATLAB toolbox for optimization over symmetric cones Optim. Methods Softw., 11/12 (1999), 625-653. doi: 10.1080/10556789908805766.  Google Scholar

[9]

Y. TianS. C. FangZ. B. Deng and W. X. Xing, Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming, Journal of Industrial and Management Optimization, 9 (2013), 703-721.  doi: 10.3934/jimo.2013.9.703.  Google Scholar

[10]

S. Y. WangY. J. Liu and Y. Jiang, A majorized penalty approach to inverse linear second order cone programming problems, Journal of Industrial and Management Optimization, 10 (2014), 965-976.  doi: 10.3934/jimo.2014.10.965.  Google Scholar

[11]

E. Welzl, Smalleat enclosing disks (balls and ellipsoids), in New Results and New Trends in Computer Science, Springer-Verlag, 1991,359–370. doi: 10.1007/BFb0038202.  Google Scholar

[12]

S. XuR. Freund and J. Sun, Solution methodologies for the smallest enclosing circle problem, Comput. Optim. Appl., 25 (2003), 283-292.  doi: 10.1023/A:1022977709811.  Google Scholar

[13]

Y. ZhangY. JiangL. Zhang and J. Zhang, A perturbation approach for an inverse linear second-order cone programming, Journal of Industrial and Management Optimization, 9 (2013), 171-189.  doi: 10.3934/jimo.2013.9.171.  Google Scholar

Figure 1.  The smallest enclosing circle for eight circles by the cutting plane method
Table 1.  Computational results for 12800 circles by the cutting plane method
k R (x, y) Time
1 20.9058731071536 (0.545051135217305, 1.44782921739902) 3122
2 20.9105991582134 (0.299192662259897, 1.31150575665027) 3666
3 20.9125332765331 (0.298922131451905, 1.31135826866618) 4291
4 20.9125332765331 (0.298922131451905, 1.31135826866618) 4934
k R (x, y) Time
1 20.9058731071536 (0.545051135217305, 1.44782921739902) 3122
2 20.9105991582134 (0.299192662259897, 1.31150575665027) 3666
3 20.9125332765331 (0.298922131451905, 1.31135826866618) 4291
4 20.9125332765331 (0.298922131451905, 1.31135826866618) 4934
Table 2.  The number of iterations on the cutting plane method
m Average Maximum Minimum
50 3.14 5 2
200 3.08 4 3
800 3.22 4 3
3200 3.16 5 3
12800 3.46 7 3
m Average Maximum Minimum
50 3.14 5 2
200 3.08 4 3
800 3.22 4 3
3200 3.16 5 3
12800 3.46 7 3
Table 3.  Objective function value
Problem Obj Value
m SOCP QP Algorithm 1
50 11.2096459 11.2096469 11.2096459
200 14.3832518 14.3832526 14.3832516
800 16.9222886 16.9222890 16.9222882
3200 19.1035735 19.1035733 19.1035728
12800 20.9684117 Out of Memory 20.9684103
Problem Obj Value
m SOCP QP Algorithm 1
50 11.2096459 11.2096469 11.2096459
200 14.3832518 14.3832526 14.3832516
800 16.9222886 16.9222890 16.9222882
3200 19.1035735 19.1035733 19.1035728
12800 20.9684117 Out of Memory 20.9684103
Table 4.  Average CPU time of three methods
Problem Time
m SOCP QP Algorithm 1
50 82.2 88.4 79.8
200 115.0 180.2 103.4
800 257.4 1859.4 254.6
3200 1041.6 34883.9 973.1
12800 8555.7 Out of Memory 5024.6
Problem Time
m SOCP QP Algorithm 1
50 82.2 88.4 79.8
200 115.0 180.2 103.4
800 257.4 1859.4 254.6
3200 1041.6 34883.9 973.1
12800 8555.7 Out of Memory 5024.6
[1]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[2]

Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020377

[3]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164

[4]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340

[5]

Soniya Singh, Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of second order impulsive systems with state-dependent delay in Banach spaces. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020103

[6]

Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272

[7]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444

[8]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168

[9]

Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045

[10]

Kihoon Seong. Low regularity a priori estimates for the fourth order cubic nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5437-5473. doi: 10.3934/cpaa.2020247

[11]

Youshan Tao, Michael Winkler. Critical mass for infinite-time blow-up in a haptotaxis system with nonlinear zero-order interaction. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 439-454. doi: 10.3934/dcds.2020216

[12]

Jun Zhou. Lifespan of solutions to a fourth order parabolic PDE involving the Hessian modeling epitaxial growth. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5581-5590. doi: 10.3934/cpaa.2020252

[13]

Mathew Gluck. Classification of solutions to a system of $ n^{\rm th} $ order equations on $ \mathbb R^n $. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5413-5436. doi: 10.3934/cpaa.2020246

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (174)
  • HTML views (518)
  • Cited by (0)

Other articles
by authors

[Back to Top]