{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:04:51Z","timestamp":1760241891466,"version":"build-2065373602"},"reference-count":17,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2018,10,16]],"date-time":"2018-10-16T00:00:00Z","timestamp":1539648000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"publisher","award":["61433012","U1435215"],"award-info":[{"award-number":["61433012","U1435215"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Shenzhen basic research","award":["JCYJ20160229195940462"],"award-info":[{"award-number":["JCYJ20160229195940462"]}]},{"name":"the Innovation of Science and Technology Commission of Shenzhen Municipality","award":["JCYJ20150521144320984"],"award-info":[{"award-number":["JCYJ20150521144320984"]}]},{"name":"Hong Kong GRF","award":["17210017"],"award-info":[{"award-number":["17210017"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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    .<\/jats:p>","DOI":"10.3390\/a11100156","type":"journal-article","created":{"date-parts":[[2018,10,16]],"date-time":"2018-10-16T11:07:51Z","timestamp":1539688071000},"page":"156","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Online Uniformly Inserting Points on the Sphere"],"prefix":"10.3390","volume":"11","author":[{"given":"Rong","family":"Zhou","sequence":"first","affiliation":[{"name":"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"},{"name":"University of Chinese Academy of Sciences, 19(A) Yuquan Road, Shijingshan District, Beijing 100049, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chun","family":"Chen","sequence":"additional","affiliation":[{"name":"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"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liqun","family":"Sun","sequence":"additional","affiliation":[{"name":"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"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1082-9333","authenticated-orcid":false,"given":"Francis C. M.","family":"Lau","sequence":"additional","affiliation":[{"name":"Department of Computer Science, The University of Hong Kong, Pokfulam, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sheung-Hung","family":"Poon","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Nottingham Ningbo China, 199 Taikang East Road, Ningbo 315100, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yong","family":"Zhang","sequence":"additional","affiliation":[{"name":"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"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,10,16]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/PL00009472","article-title":"More Optimal Packings of Equal Circles in a Square","volume":"22","author":"Nurmela","year":"1999","journal-title":"Discret. Comput. Geom."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/S0925-7721(02)00099-8","article-title":"A circle packing algorithm","volume":"25","author":"Collins","year":"2003","journal-title":"Comput. Geom. Theory Appl."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"2287","DOI":"10.1090\/S0025-5718-10-02358-6","article-title":"Asymptotics of greedy energy points","volume":"79","author":"Saff","year":"2010","journal-title":"Math. Comput."},{"key":"ref_4","unstructured":"Matousek, J. (1999). Geometric Discrepancy: An Illustrated Guide, Springer."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Chazelle, B. (2000). The Discrepancy Method: Randomness and Complexity, Cambridge University Press.","DOI":"10.1017\/CBO9780511626371"},{"key":"ref_6","first-page":"990","article-title":"Point sets on the sphere \ud835\udd4a2 with small spherical cap discrepancy","volume":"48","author":"Aistleitner","year":"2012","journal-title":"Discret. Comput. Geom."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1090\/S0025-5718-1993-1155573-5","article-title":"Spherical designs, discrepancy and numerical integration","volume":"60","author":"Grabner","year":"1993","journal-title":"Math. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"2348","DOI":"10.1093\/ietisy\/e89-d.8.2348","article-title":"Inserting points uniformly at every instance","volume":"89","author":"Teramoto","year":"2006","journal-title":"IEICE Trans. Inf. Syst."},{"key":"ref_9","unstructured":"Asano, T., and Teramoto, S. (2007, January 8\u201311). On-line uniformity of points. Proceedings of the Book of Abstracts for 8th Hellenic-European Conference on Computer Mathematics and its Applications, Athens, Greece."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Asano, T. (2008). Online uniformity of integer points on a line. Inf. Proc. Lett.","DOI":"10.1016\/j.ipl.2008.09.008"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"773","DOI":"10.1016\/j.ipl.2011.05.001","article-title":"Uniformly inserting points on square grid","volume":"111","author":"Zhang","year":"2011","journal-title":"Inf. Proc. Lett."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"2138","DOI":"10.1137\/15M1051300","article-title":"Uniformity of point samples in metric spaces using gap ratio","volume":"31","author":"Bishnu","year":"2017","journal-title":"SIAM J. Discret. Math."},{"key":"ref_13","unstructured":"Chen, C., Lau, F.C., Poon, S.H., Zhang, Y., and Zhou, R. (2017, January 29\u201331). Online Inserting Points Uniformly on the Sphere. Proceedings of the International Workshop on Algorithms and Computation, Hsinchu, Taiwan."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1080\/14786440409463107","article-title":"On the structure of the atom: An investigation of the stability and periods of oscillation of a number of corpuscles arranged at equal intervals around the circumference of a circle; with application of the results to the theory of atomic structure","volume":"7","author":"Thomson","year":"1904","journal-title":"Lond. Edinb. Dublin Philos. Mag. J. Sci."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1145\/377939.377945","article-title":"An efficient method for generating uniformly distributed points on the surface of an n-dimensional sphere","volume":"2","author":"Hicks","year":"1959","journal-title":"Commun. ACM"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.jocs.2010.12.003","article-title":"Analytically exact spiral scheme for generating uniformly distributed points on the unit sphere","volume":"2","author":"Koay","year":"2011","journal-title":"J. Comput. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1016\/j.jocs.2014.06.008","article-title":"Distributing points uniformly on the unit sphere under a mirror reflection symmetry constraint","volume":"5","author":"Koay","year":"2014","journal-title":"J. Comput. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/10\/156\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:26:01Z","timestamp":1760196361000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/10\/156"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,16]]},"references-count":17,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2018,10]]}},"alternative-id":["a11100156"],"URL":"https:\/\/doi.org\/10.3390\/a11100156","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2018,10,16]]}}}