TY - GEN
T1 - Online inserting points uniformly on the sphere
AU - Chen, Chun
AU - Lau, Francis C.M.
AU - Poon, Sheung Hung
AU - Zhang, Yong
AU - Zhou, Rong
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - In many scientific and engineering applications, there are occasions where points need to be inserted uniformly onto a sphere. Previous works on uniform point insertion mainly focus on the offline version, i.e., to compute N positions on the sphere for a given interger N with the objective to distribute these points as uniformly as possible. An example application is the Thomson problem where the task is to find the minimum electrostatic potential energy configuration of N electrons constrained on the surface of a sphere. In this paper, we study the online version of uniformly inserting points on the sphere. The number of inserted points is not known in advance, which means the points are inserted one at a time and the insertion algorithm does not know when to stop. As before, the objective is achieve a distribution of the points that is as uniform as possible at each step. The uniformity is measured by the gap ratio, the ratio between the maximal gap and the minimal gap of any pair of inserted points. We give a two-phase algorithm by using the structure of the regular dodecahedron, of which the gap ratio is upper bounded by 5.99. This is the first result for online uniform point insertion on the sphere.
AB - In many scientific and engineering applications, there are occasions where points need to be inserted uniformly onto a sphere. Previous works on uniform point insertion mainly focus on the offline version, i.e., to compute N positions on the sphere for a given interger N with the objective to distribute these points as uniformly as possible. An example application is the Thomson problem where the task is to find the minimum electrostatic potential energy configuration of N electrons constrained on the surface of a sphere. In this paper, we study the online version of uniformly inserting points on the sphere. The number of inserted points is not known in advance, which means the points are inserted one at a time and the insertion algorithm does not know when to stop. As before, the objective is achieve a distribution of the points that is as uniform as possible at each step. The uniformity is measured by the gap ratio, the ratio between the maximal gap and the minimal gap of any pair of inserted points. We give a two-phase algorithm by using the structure of the regular dodecahedron, of which the gap ratio is upper bounded by 5.99. This is the first result for online uniform point insertion on the sphere.
UR - http://www.scopus.com/inward/record.url?scp=85014303589&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-53925-6_19
DO - 10.1007/978-3-319-53925-6_19
M3 - Conference contribution
AN - SCOPUS:85014303589
SN - 9783319539249
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 243
EP - 253
BT - WALCOM
A2 - Rahman, Md. Saidur
A2 - Yen, Hsu-Chun
A2 - Poon, Sheung-Hung
PB - Springer Verlag
T2 - 11th International Conference and Workshops on Algorithms and Computation, WALCOM 2017
Y2 - 29 March 2017 through 31 March 2017
ER -