From offline to online: Sequentially distributing points on a sphere

Shu Wang; Xiaoli Cen; Shu Wang; Xiaoli Cen

doi:10.3934/jimo.2026105

Journal of Industrial and Management Optimization

2026, Volume 22, Issue 6: 2866-2877. doi: 10.3934/jimo.2026105

Previous Article Next Article

Research article

From offline to online: Sequentially distributing points on a sphere

Shu Wang ¹,
Xiaoli Cen ^{2
,
,}

1.
School of Mathematics and Physics, North China Electric Power University, Beijing, 102206, P. R. China
2.
School of Mathematics and Statistics, Taiyuan Normal University, Jinzhong, 030619, P. R. China

Received: 15 February 2026 Revised: 11 May 2026 Accepted: 14 May 2026 Published: 25 May 2026
90C26, 90C59

We study the online version of the point distribution problem on a sphere, where the points arrive sequentially and must be placed irrevocably. The underlying offline problems, such as the Fekete problem, Tammes problem, Thomson problem, and Fejes Toth problem, are computationally intractable. To address this, we establish a unified model and propose a novel online algorithmic framework. The algorithm can provide a theoretical approximation ratio, bounding the performance gap between our online solution and the offline optimum. As an application, we derive concrete approximation guarantees for the aforementioned classical problems.
- online distribution,
- sphere,
- approximation algorithm
Citation: Shu Wang, Xiaoli Cen. From offline to online: Sequentially distributing points on a sphere[J]. Journal of Industrial and Management Optimization, 2026, 22(6): 2866-2877. doi: 10.3934/jimo.2026105

Related Papers:

Abstract

We study the online version of the point distribution problem on a sphere, where the points arrive sequentially and must be placed irrevocably. The underlying offline problems, such as the Fekete problem, Tammes problem, Thomson problem, and Fejes Toth problem, are computationally intractable. To address this, we establish a unified model and propose a novel online algorithmic framework. The algorithm can provide a theoretical approximation ratio, bounding the performance gap between our online solution and the offline optimum. As an application, we derive concrete approximation guarantees for the aforementioned classical problems.

References

[1]	J. B. Hiriart-Urruty, A new series of conjectures and open questions in optimization and matrix analysis, ESAIM:COCV, 15 (2009), 454–470. https://doi.org/10.1051/cocv:2008040 doi: 10.1051/cocv:2008040
[2]	E. B. Satff, A. B. J. Kuijlaars, Distributing many points on the sphere, Math. Intell., 19 (1997), 5–11. https://doi.org/10.1007/BF03024331 doi: 10.1007/BF03024331
[3]	P. M. L. Tammes, On the origin of number and arrangement of the places of exit on the surface of pollen grains, J. H. De Bussy., 27 (1930), 1–84.
[4]	Y. P. Wang, Y. Xia, Semidefinite programming relaxation for the Tammes problem, Proc. of the 10th Annual ORSC Conf., 2010,117–123.
[5]	R. A. Rankin, The closet packing of spherical caps in n dimensions, Proc. Glasg. Math. Assoc., 2 (1995), 139–144. https://doi.org/10.1017/S2040618500033219 doi: 10.1017/S2040618500033219
[6]	T. Ericson, V. Zinoviev, Codes on euclidean spheres, Netherlands, 2001.
[7]	J. Chen, B. Li, Y. K. Li, Efficient approximations for the online dispersion problem, SIAM J. Comput., 48 (2019), 373–416. https://doi.org/10.1137/17M1131027 doi: 10.1137/17M1131027
[8]	D. Laat, Moment methods in energy minimization: New bounds for Riesz minimal energy problems, Trans. Amer. Math. Soc., 373 (2020), 1407–1453. https://doi.org/10.1090/tran/7976 doi: 10.1090/tran/7976
[9]	D. Bilyk, M. Mastrianni, R. W. Matzke, S. Steinerberger, Polarization and greedy energy on the sphere, arXiv preprint arXiv: 2302.13067, 2023. https://doi.org/10.48550/arXiv.2302.13067
[10]	D. Minati, S. Singh, Online hitting of unit balls and hypercubes in $R^d$ using points from $Z^d$, Theor. Comput. Sci., 992 (2024), 114452. https://doi.org/10.1016/j.tcs.2024.114452 doi: 10.1016/j.tcs.2024.114452
[11]	C. N. Lintzmayer, F. K. Miyazawa, E. C. Xavier, Online circle and sphere packing, Theor. Comput. Sci., 776 (2019), 75–94. https://doi.org/10.1016/j.tcs.2019.01.004 doi: 10.1016/j.tcs.2019.01.004
[12]	R. Schaback, Multivariate interpolation and approximation by translates of a basis function, Singapore, 1995.
[13]	S. Wang, Y. Xia, On the ball-constrained weighted maximin dispersion problem, SIAM J. Optim., 26 (2016), 1565–1588. https://doi.org/10.1137/15M1047167 doi: 10.1137/15M1047167
[14]	B. Awerbuch, Y. Azar, S. Plotkin, Throughput-competitive on-line routing, Proc. Annu. IEEE Symp. Found. Comput. Sci., 1993, 32–40. https://doi.org/10.1109/SFCS.1993.366884
[15]	N. Buchbinder, J. Naor, The design of competitive online algorithms via a primal-dual approach, Found. Trends Theor. Comput. Sci., 3 (2009), 93–263. https://doi.org/10.1561/0400000024 doi: 10.1561/0400000024
[16]	C. Karande, A. Mehta, P. Tripathi, Online bipartite matching with unknown distributions, Proc. 43rd Annu. ACM Symp. Theory Comput., 2011, 587–596. https://doi.org/10.1145/1993636.1993715
[17]	A. Mehta, A. Saberi, U. Vazirani, V. Vazirani, Adwords and generalized on-line matching, Proc. 46th Annu. IEEE Symp. Found. Comput. Sci., 2005, 264–273. https://doi.org/10.1109/SFCS.2005.12
[18]	S. Agrawal, Z. Z. Wang, Y. Y. Ye, A dynamic near-optimal algorithm for online linear programming, Oper. Res., 62 (2009), 876–890. https://doi.org/10.1287/opre.2014.1289 doi: 10.1287/opre.2014.1289
[19]	K. Ball, An elementary introduction to modern convex geometry, Flavors of Geometry, 1997.

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)