Research Center for High Performance Computing, Joint Engineering Research Center for Health Big Data Intelligent Analysis Technology, Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, 1068 Xueyuan Avenue, Shenzhen University Town, Shenzhen 518055, China
Chun Chen
Research Center for High Performance Computing, Joint Engineering Research Center for Health Big Data Intelligent Analysis Technology, Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, 1068 Xueyuan Avenue, Shenzhen University Town, Shenzhen 518055, China
Liqun Sun
Research Center for High Performance Computing, Joint Engineering Research Center for Health Big Data Intelligent Analysis Technology, Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, 1068 Xueyuan Avenue, Shenzhen University Town, Shenzhen 518055, China
Francis C. M. Lau
Department of Computer Science, The University of Hong Kong, Pokfulam, Hong Kong, China
Sheung-Hung Poon
School of Computer Science, University of Nottingham Ningbo China, 199 Taikang East Road, Ningbo 315100, China
Yong Zhang
Research Center for High Performance Computing, Joint Engineering Research Center for Health Big Data Intelligent Analysis Technology, Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, 1068 Xueyuan Avenue, Shenzhen University Town, Shenzhen 518055, China
Uniformly inserting points on the sphere has been found useful in many scientific and engineering fields. Different from the offline version where the number of points is known in advance, we consider the online version of this problem. The requests for point insertion arrive one by one and the target is to insert points as uniformly as possible. To measure the uniformity we use gap ratio which is defined as the ratio of the maximal gap to the minimal gap of two arbitrary inserted points. We propose a two-phase online insertion strategy with gap ratio of at most 3.69 . Moreover, the lower bound of the gap ratio is proved to be at least 1.78 .