A reformulation-linearization based algorithm for the smallest enclosing circle problem

Yi Jiang; Yuan Cai

doi:10.3934/jimo.2020136

Article Contents

2021, Volume 17, Issue 6: 3633-3644. Doi: 10.3934/jimo.2020136

This issue Previous Article Analysis of

$ D $

$ BMAP/G/1 $

queueing system under

$ N $

-policy and its cost optimization Next Article Maxillofacial surgical simulation system with haptic feedback

A reformulation-linearization based algorithm for the smallest enclosing circle problem

Yi Jiang^, and
Yuan Cai

School of Mathematical Sciences and VC/VR Key Lab, Sichuan Normal University, Chengdu, Sichuan 610066, China

^* Corresponding author: yijiang103@163.com
^* Corresponding author: yijiang103@163.com

Received: February 29, 2020

Revised: May 31, 2020

Early access: August 2020

Published: November 2021

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

Abstract Full Text(HTML) Figure(3) / Table(6) Related Papers Cited by

Abstract

In this paper, an effective algorithm based on the reformulation-linearization technique (RLT) is developed to solve the smallest enclosing circle problem. Extensive computational experiments demonstrate that the algorithm based on the RLT outperforms the existing algorithms in terms of the solution time and quality in average.

Keywords:

Mathematics Subject Classification: Primary: 90C30.

Citation:

FullText(HTML)

Figure 1. The error for under-estimating a square

Download: Full-size image PowerPoint slide

Figure 2. Average CPU time of three methods in 2D

Download: Full-size image PowerPoint slide

Figure 3. Average CPU time of three methods in 3D

Download: Full-size image PowerPoint slide

Table 1. Computational results for 30000 circles by Algorithm Ⅰ in 2D

k	R	(x, y)	Time
$ 1 $	22.39739458	(-0.23034495, 1.54096380)	1256
$ 2 $	22.45136334	(-0.22954489, 1.54016746)	4437
$ 3 $	22.45378444	(-0.22950900, 1.54013173)	4705
$ 4 $	22.45382627	(-0.22950838, 1.54013111)	4817

| Show Table

DownLoad: CSV

Table 2. The number of iterations on Algorithm Ⅰ in 2D

Problem	Iteration
m	Average	Maximum	Minimum
$ 30 $	4.48	6	4
$ 300 $	4.12	5	3
$ 3000 $	3.78	4	3
$ 30000 $	3.70	4	3

| Show Table

DownLoad: CSV

Table 3. Objective function value and average CPU time of four methods in 2D

Problem	SOCP		CP		SDPT3		Algorithm Ⅰ
m	Obj Value	Time	Obj Value	Time	Obj Value	Time	Obj Value	Time
$ 30 $	9.13411	128.98	9.13411	125.80	9.13411	1744.45	9.13411	66.50
$ 300 $	15.05421	179.80	15.05421	165.26	15.05421	6848.30	15.05421	70.60
$ 3000 $	18.31612	781.82	18.31612	918.92	18.31612	65688.71	18.31612	530.66
$ 30000 $	21.21799	25641.96	21.21799	15716.18	21.21799	1548266.51	21.21799	5052.26

| Show Table

DownLoad: CSV

Table 4. Computational results for 20000 balls by Algorithm Ⅰ in 3D

k	R	(x, y, z)	Time
$ 1 $	21.18238030	(-0.41033399, 0.50362615, -1.77470296)	2682
$ 2 $	21.25471838	(-0.40932025, 0.50524350, -1.77617447)	4658
$ 3 $	21.25805248	(-0.40927352, 0.50531805, -1.77624230)	6623
$ 4 $	21.25808485	(-0.40927307, 0.50531877, -1.77624296)	10525
$ 5 $	21.25808512	(-0.40927306, 0.50531878, -1.77624296)	14668

| Show Table

DownLoad: CSV

Table 5. The number of iterations on Algorithm Ⅰ in 3D

Problem	Iteration
m	Average	Maximum	Minimum
$ 20 $	8.96	13	5
$ 200 $	6.54	11	4
$ 2000 $	6.68	12	4
$ 20000 $	5.84	10	4

| Show Table

DownLoad: CSV

Table 6. Objective function value and average CPU time of four methods in 3D

Problem	SOCP		CP		SDPT3		Algorithm 1
m	Obj Value	Time	Obj Value	Time	Obj Value	Time	Obj Value	Time
$ 20 $	10.20133	131.26	10.20133	138.96	10.20133	1589.39	10.20133	120.92
$ 200 $	13.90667	168.56	13.90667	251.66	13.90667	5157.42	13.90667	123.88
$ 2000 $	16.47548	633.00	16.47548	1694.06	16.47548	43022.79	16.47548	161.02
$ 20000 $	20.54257	16953.74	20.54257	18185.18	20.54257	907801.50	20.54257	1462.04

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	C. Audet, P. Hansen, B. Jaumard and G. Savard, A branch and cut algorithm for nonconvex quadratically constrained quadratic programming, Math. Program., 87 (2000), 131-152. doi: 10.1007/s101079900106.
[2]	M. de Berg, O. Cheong, M. van Kreveld and M. Overmars, Computational Geometry: Algorithms and Applications, Springer, Berlin, Heidelberg, 2008. doi: 10.1007/978-3-540-77974-2.
[3]	P. Chrystal, On the problem to construct the minimum circle enclosing n given points in a plane, Proceedings of the Edinburgh Mathematical Society, 3 (1884), 30-33. doi: 10.1017/S0013091500037238.
[4]	D. W. Hearn and J. Vijay, Efficient algorithms for the (weighted) minimum circle problem, Oper. Res., 30 (1982), 777-795. doi: 10.1287/opre.30.4.777.
[5]	Y. Jiang, C. Luo and S. G. Ling, An efficient cutting plane algorithm for the smallest enclosing circle problem, J. Ind. Manag. Optim., 13 (2017), 147-153. doi: 10.3934/jimo.2016009.
[6]	H. D. Sherali and C. H. Tuncbilek, Global optimization algorithm for polynomial programming using a reformulation-linearization technique, J. Global Optim., 2 (1992), 101-112. doi: 10.1007/BF00121304.
[7]	H. D. Sherali and C. H. Tuncbilek, Reformulation-convexification approach for solving nonconvex quadratic programming problems, J. Global Optim., 7 (1995), 1-31. doi: 10.1007/BF01100203.
[8]	H. D. Sherali and C. H. Tuncbilek, Comparison of two reformulation-linearization technique based linear programming relaxations for polynomial programming problems, J. Global Optim., 10 (1997), 381-390. doi: 10.1023/A:1008237515535.
[9]	S. H. Pan and X. S. Li, An efficient algorithm for the smallest enclosing ball problem in high dimension, Appl. Math. Comput., 172 (2006), 49-61. doi: 10.1016/j.amc.2005.01.127.
[10]	S. Skyum, A simple algorithm for computing the smallest enclosing circle, Inform. Process. Lett., 37 (1991), 121-125. doi: 10.1016/0020-0190(91)90030-L.
[11]	J. Sturm, Using SeDuMi 1.02, A MATLAB toolbox for optimization over symmetric cones. Interior point methods, Optim. Methods Softw. 11/12 (1999), 625-653. doi: 10.1080/10556789908805766.
[12]	J. J. Sylvester, A question in the geometry of situation, Quart. J. Math., 1 (1857), 79.
[13]	E. Welzl, Smallest enclosing disks (balls and ellipsoids), in New Results and New Trends in Computer Science, Springer, Berlin, 1991,359-370. doi: 10.1007/BFb0038202.
[14]	S. Xu, R. Freund and J. Sun, Solution methodologies for the smallest enclosing circle problem, Comput. Optim. Appl., 25 (2003), 283-292. doi: 10.1023/A:1022977709811.
[15]	E. A. Yildirim, Two algorithms for the minimum enclosing ball problem, SIAM J. Optim., 19 (2008), 1368-1391. doi: 10.1137/070690419.
[16]	G. Zhou, K. C. Tohemail and J. Sun, Efficient algorithms for the smallest enclosing ball problem, Comput. Optim. Appl., 30 (2005), 147-160. doi: 10.1007/s10589-005-4565-7.