Algorithms (Oct 2018)

Online Uniformly Inserting Points on the Sphere

  • Rong Zhou,
  • Chun Chen,
  • Liqun Sun,
  • Francis C. M. Lau,
  • Sheung-Hung Poon,
  • Yong Zhang

DOI
https://doi.org/10.3390/a11100156
Journal volume & issue
Vol. 11, no. 10
p. 156

Abstract

Read online

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 .

Keywords