C-VoNNI: a precise fingerprint construction for indoor positioning systems using natural neighbor methods with clustering-based Voronoi diagrams

Yun Fen Yong, Chee Keong Tan, Ian K.T. Tan, Su Wei Tan

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)


Indoor positioning is crucial for everyday life, and received signal strength-based fingerprint localization is the most effective method. However, updating the fingerprint database is laborious, as changes in indoor layout would render the initial radio map outdated. To address this issue, we propose a precise radio map construction method by clustering and interpolating virtual fingerprints. The affinity propagation clustering algorithm and Voronoi diagram are used to group fingerprints with similar characteristics, mitigating the negative effects of multipath fading and shadowing caused by changes in the indoor layout. After generating synthetic reference points using the gradient extrapolation method to expand the convex hull, natural neighbor interpolation can construct accurate virtual fingerprints. Experimental results show that our proposed method outperformed both inverse distance weighting and Kriging interpolation by up to 33% in localization accuracy across diverse environments. This approach enables efficient radio map generation with comparable localization accuracy to the original radio map without extensive site surveys.

Original languageEnglish
Pages (from-to)10667–10694
Number of pages28
JournalJournal of Supercomputing
Publication statusPublished - May 2024


  • Affinity propagation clustering
  • Convex hull
  • Indoor positioning
  • Natural neighbor interpolation
  • Radio map construction
  • Voronoi diagram

Cite this