{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:28Z","timestamp":1740109588152,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,3,22]],"date-time":"2022-03-22T00:00:00Z","timestamp":1647907200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,22]],"date-time":"2022-03-22T00:00:00Z","timestamp":1647907200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/R018472\/1"],"award-info":[{"award-number":["EP\/R018472\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The problem of uniformly placing <jats:italic>N<\/jats:italic> points onto a sphere finds applications in many areas. For example, points on the sphere correspond to unit quaternions as well as to the group of rotations SO(3) and the online version of generating uniform rotations (known as \u201cincremental generation\u201d) plays a crucial role in a large number of engineering applications ranging from robotics and aeronautics to computer graphics. An online version of this problem was recently studied with respect to the <jats:italic>gap ratio<\/jats:italic> as a measure of uniformity. The first online algorithm of Chen et al. was upper-bounded by 5.99 and later improved to 3.69, which is achieved by considering a circumscribed dodecahedron followed by a recursive decomposition of each face. In this paper we provide a more efficient tessellation technique based on the regular icosahedron, which improves the upper-bound for the online version of this problem, decreasing it to approximately 2.84. Moreover, we show that the lower bound for the gap ratio of placing at least three points is <jats:inline-formula><jats:alternatives><jats:tex-math>$$({1+\\sqrt{5}})\/2\\approx 1.618$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mrow>\n                      <mml:mn>1<\/mml:mn>\n                      <mml:mo>+<\/mml:mo>\n                      <mml:msqrt>\n                        <mml:mn>5<\/mml:mn>\n                      <\/mml:msqrt>\n                    <\/mml:mrow>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>\u2248<\/mml:mo>\n                    <mml:mn>1.618<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and for at least four points is no less than 1.726.<\/jats:p>","DOI":"10.1007\/s00454-022-00384-x","type":"journal-article","created":{"date-parts":[[2022,3,22]],"date-time":"2022-03-22T14:04:18Z","timestamp":1647957858000},"page":"1124-1146","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Towards Uniform Online Spherical Tessellations"],"prefix":"10.1007","volume":"67","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2620-635X","authenticated-orcid":false,"given":"Paul C.","family":"Bell","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Potapov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,3,22]]},"reference":[{"issue":"1","key":"384_CR1","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.ipl.2008.09.008","volume":"109","author":"T Asano","year":"2008","unstructured":"Asano, T.: Online uniformity of integer points on a line. Inf. Process. Lett. 109(1), 57\u201360 (2008)","journal-title":"Inf. Process. Lett."},{"key":"384_CR2","unstructured":"Asano, T., Teramoto, S.: On-line uniformity of points. In: 8th Hellenic-European Conference on Computer Mathematics and Its Applications (Athens 2007), pp. 21\u201322 (2007)"},{"issue":"11","key":"384_CR3","doi-asserted-by":"publisher","first-page":"1353","DOI":"10.1016\/j.ic.2008.06.004","volume":"206","author":"P Bell","year":"2008","unstructured":"Bell, P., Potapov, I.: Reachability problems in quaternion matrix and rotation semigroups. Inf. Comput. 206(11), 1353\u20131361 (2008)","journal-title":"Inf. Comput."},{"key":"384_CR4","doi-asserted-by":"crossref","unstructured":"Bell, P.C., Potapov, I.: Towards uniform online spherical tessellations. In: 15th Conference on Computability in Europe (Durham 2019). Lecture Notes in Computer Science, vol. 11558, pp. 120\u2013131. Springer, Cham (2019)","DOI":"10.1007\/978-3-030-22996-2_11"},{"issue":"1","key":"384_CR5","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/s10474-013-0339-3","volume":"142","author":"AV Bondarenko","year":"2014","unstructured":"Bondarenko, A.V., Hardin, D.P., Saff, E.B.: Mesh ratios for best-packing and limits of minimal energy configurations. Acta Math. Hungar. 142(1), 118\u2013131 (2014)","journal-title":"Acta Math. Hungar."},{"issue":"3","key":"384_CR6","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/j.jco.2015.02.003","volume":"31","author":"JS Brauchart","year":"2015","unstructured":"Brauchart, J.S., Grabner, P.J.: Distributing many points on spheres: minimal energy and designs. J. Complex. 31(3), 293\u2013326 (2015)","journal-title":"J. Complex."},{"key":"384_CR7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626371","volume-title":"The Discrepancy Method. Randomness and Complexity","author":"B Chazelle","year":"2000","unstructured":"Chazelle, B.: The Discrepancy Method. Randomness and Complexity. Cambridge University Press, Cambridge (2000)"},{"key":"384_CR8","doi-asserted-by":"crossref","unstructured":"Chen, Ch., Lau, F.C.M., Poon, Sh.-H., Zhang, Y., Zhou, R.: Online inserting points uniformly on the sphere. In: WALCOM: Algorithms and Computation (Hsinchu 2017). Lecture Notes in Computer Science, vol. 10167, pp. 243\u2013253. Springer, Cham (2017)","DOI":"10.1007\/978-3-319-53925-6_19"},{"issue":"4","key":"384_CR9","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1038\/scientificamerican1091-54","volume":"265","author":"RF Curl","year":"1991","unstructured":"Curl, R.F., Smalley, R.E.: Fullerenes. Sci. Am. 265(4), 54\u201363 (1991)","journal-title":"Sci. Am."},{"issue":"4","key":"384_CR10","doi-asserted-by":"publisher","first-page":"1218","DOI":"10.1007\/s00454-021-00305-4","volume":"66","author":"U Etayo","year":"2021","unstructured":"Etayo, U.: Spherical cap discrepancy of the diamond ensemble. Discrete Comput. Geom. 66(4), 1218\u20131238 (2021)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"384_CR11","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/s00037-005-0193-y","volume":"14","author":"V Guruswami","year":"2005","unstructured":"Guruswami, V., Micciancio, D., Regev, O.: The complexity of the covering radius problem. Comput. Complex. 14(2), 90\u2013121 (2005)","journal-title":"Comput. Complex."},{"issue":"10","key":"384_CR12","first-page":"1186","volume":"51","author":"DP Hardin","year":"2004","unstructured":"Hardin, D.P., Saff, E.B.: Discretizing manifolds via minimum energy points. Not. Am. Math. Soc. 51(10), 1186\u20131194 (2004)","journal-title":"Not. Am. Math. Soc."},{"issue":"5","key":"384_CR13","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1016\/j.jocs.2014.06.008","volume":"5","author":"ChG Koay","year":"2014","unstructured":"Koay, Ch.G.: Distributing points uniformly on the unit sphere under a mirror reflection symmetry constraint. J. Comput. Sci. 5(5), 696\u2013700 (2014)","journal-title":"J. Comput. Sci."},{"issue":"suppl.","key":"384_CR14","doi-asserted-by":"publisher","first-page":"S149","DOI":"10.1002\/cpa.3160390710","volume":"39","author":"A Lubotzky","year":"1986","unstructured":"Lubotzky, A., Phillips, R., Sarnak, P.: Hecke operators and distributing points on the sphere. I. Commun. Pure Appl. Math. 39(suppl.), S149\u2013S186 (1986)","journal-title":"Commun. Pure Appl. Math."},{"key":"384_CR15","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J.: Geometric Discrepancy. An Illustrated Guide. Algorithms and Combinatorics, vol.\u00a018. Springer, Berlin (1999)","DOI":"10.1007\/978-3-642-03942-3"},{"issue":"6","key":"384_CR16","doi-asserted-by":"publisher","first-page":"647","DOI":"10.4310\/MRL.1994.v1.n6.a3","volume":"1","author":"EA Rakhmanov","year":"1994","unstructured":"Rakhmanov, E.A., Saff, E.B., Zhou, Y.M.: Minimal discrete energy on the sphere. Math. Res. Lett. 1(6), 647\u2013662 (1994)","journal-title":"Math. Res. Lett."},{"issue":"1","key":"384_CR17","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/BF03024331","volume":"19","author":"EB Saff","year":"1997","unstructured":"Saff, E.B., Kuijlaars, A.B.J.: Distributing many points on a sphere. Math. Intell. 19(1), 5\u201311 (1997)","journal-title":"Math. Intell."},{"key":"384_CR18","doi-asserted-by":"crossref","unstructured":"Shoemake, K.: Uniform random rotations. In: Graphics Gems III, pp. 124\u2013132. Academic Press, Boston (1992)","DOI":"10.1016\/B978-0-08-050755-2.50036-1"},{"issue":"3","key":"384_CR19","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/BF02570704","volume":"14","author":"NJA Sloane","year":"1995","unstructured":"Sloane, N.J.A., Hardin, R.H., Duff, T.D.S., Conway, J.H.: Minimal-energy clusters of hard spheres. Discrete Comput. Geom. 14(3), 237\u2013259 (1995)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"384_CR20","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/BF03025291","volume":"20","author":"S Smale","year":"1998","unstructured":"Smale, S.: Mathematical problems for the next century. Math. Intell. 20(2), 7\u201315 (1998)","journal-title":"Math. Intell."},{"issue":"2","key":"384_CR21","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/j.jat.2007.09.009","volume":"151","author":"X Sun","year":"2008","unstructured":"Sun, X., Chen, Zh.: Spherical basis functions and uniform distribution of points on spheres. J. Approx. Theory 151(2), 186\u2013207 (2008)","journal-title":"J. Approx. Theory"},{"key":"384_CR22","unstructured":"Tammes, P.M.L.: On the Origin of Number and Arrangement of the Places of Exit on the Surface of Pollen-Grains. Recueil des Travaux Botaniques N\u00e9erlandais, vol.\u00a027. Koninklijke Nederlandse Botanische Vereniging (1930)"},{"key":"384_CR23","doi-asserted-by":"crossref","unstructured":"Teramoto, S., Asano, T., Katoh, N., Doerr, B.: Inserting points uniformly at every instance. IEICE Trans. Inf. Syst. E89-D(8), 2348\u20132356 (2006)","DOI":"10.1093\/ietisy\/e89-d.8.2348"},{"issue":"39","key":"384_CR24","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1080\/14786440409463107","volume":"7","author":"JJ Thompson","year":"1904","unstructured":"Thompson, J.J.: 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. Philos. Mag. 7(39), 237\u2013265 (1904)","journal-title":"Philos. Mag."},{"key":"384_CR25","volume-title":"Spherical Trigonometry","author":"I Todhunter","year":"1886","unstructured":"Todhunter, I.: Spherical Trigonometry. Macmillan, London (1886)"},{"issue":"2","key":"384_CR26","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF02189312","volume":"9","author":"G Wagner","year":"1993","unstructured":"Wagner, G.: On a new method for constructing good point sets on spheres. Discrete Comput. Geom. 9(2), 111\u2013129 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"7","key":"384_CR27","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1177\/0278364909352700","volume":"29","author":"A Yershova","year":"2010","unstructured":"Yershova, A., Jain, S., Lavalle, S.M., Mitchell, J.C.: Generating uniform incremental grids on $$SO(3)$$ using the Hopf fibration. Int. J. Robot. Res. 29(7), 801\u2013812 (2010)","journal-title":"Int. J. Robot. Res."},{"issue":"16","key":"384_CR28","doi-asserted-by":"publisher","first-page":"773","DOI":"10.1016\/j.ipl.2011.05.001","volume":"111","author":"Y Zhang","year":"2011","unstructured":"Zhang, Y., Chang, Zh., Chin, F.Y.L., Ting, H.-F., Tsin, Y.H.: Uniformly inserting points on square grid. Inf. Process. Lett. 111(16), 773\u2013779 (2011)","journal-title":"Inf. Process. Lett."},{"key":"384_CR29","doi-asserted-by":"crossref","unstructured":"Zhou, R., Chen, Ch., Sun, L., Lau, F.C.M., Poon, Sh.-H., Zhang, Y.: Online uniformly inserting points on the sphere. Algorithms 11(10), #\u00a0156 (2018)","DOI":"10.3390\/a11100156"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00384-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-022-00384-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00384-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,10]],"date-time":"2022-05-10T14:08:50Z","timestamp":1652191730000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-022-00384-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,22]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["384"],"URL":"https:\/\/doi.org\/10.1007\/s00454-022-00384-x","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2022,3,22]]},"assertion":[{"value":"8 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 December 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 December 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}