Online uniformly inserting points on the sphere

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

Research output: Journal PublicationArticlepeer-review

3 Citations (Scopus)
26 Downloads (Pure)

Abstract

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.

Original languageEnglish
Article number156
JournalAlgorithms
Volume11
Issue number10
DOIs
Publication statusPublished - 1 Oct 2018

Keywords

  • Gap ratio
  • Online algorithms
  • Uniform insertion

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Numerical Analysis
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Online uniformly inserting points on the sphere'. Together they form a unique fingerprint.

Cite this