Return

Inverse Farthest Point Sampling (IFPS):
A Universal and Hierarchical Shell Representation for Discrete Data

ICMR 2025

Nayu Ding1, Yujie Lu1, Yao Huang1, Long Wan1, Yan Zhao1, Zhijun Fang1, Shen Cai1*, Lin Gao2,3*

1 School of Computer Science and Technology, Donghua University   
2 Institute of Computing Technology, Chinese Academy of Sciences    3 University of Chinese Academy of Sciences

Code

YouTube

Core Idea In One Sentence

Using only the first N FPS-sampled points, the IFPS shell can be constructed to encapsulate all the original discrete points while employing hierarchical management.


Graphical Abstract

In each iteration, IFPS processes one new FPS point (shown in red) and reconstructs a union of uniform spheres (blue, under Euclidean distance), centered at previously sampled points, to form a local shell that bounds the original data.




Implicit Sphere Tree and IFPS Shells with Increasing Sample Points

As more FPS points are used, the radii of spheres centered at existing points decrease (illustrated by concentric yellow and red circles), while a new sphere centered at the latest FPS point is incorporated.


Multi-way Tree Structure and IFPS Shells under Various Norms

IFPS enables the creation of an explicit sphere tree with $q$-way traversal using every $q^j$-th (j=0,1,2,...) iteration, requiring minimal extra storage and computation.


Algorithm

For the global shell utilizing all iterations of the IFPS process, we exhibit a fast point-in-shell algorithm shown in Algorithm 1.


Visualization


Collision Detection between Two Meshes

The scenario consists a static table and a teapot undergoing self-rotation.The teapot also falls onto the table and bounces back. Each IFPS shell for both models is constructed from 4,096 FPS points. The real-time frame rate is shown in the upper right corner.


Collision Detection in 3DGS Environment




Collision detection and real-time rendering for the designed 3DGS scenario. The dynamic entities in first scenario are 3K snowflake spheres.The real-time frame rate is shown in the upper right corner. Average Motion Control (MC) time, Collision Detection (CD) time and rendering time are shown in the lower right corner. The dynamic object in the second and third scenarios are fifty bouncing spheres and a rotating 'hotdog', respectively.



Citation

@inproceedings{IFPS,
    title={Inverse Farthest Point Sampling (IFPS): A Universal and Hierarchical Shell Representation for Discrete Data},
    author={Ding, Nayu and Lu, Yujie and Huang, Yao and Wan, Long and Zhao, Yan and Cai, Shen and Gao, Lin},
    booktitle={ACM International Conference on Multimedia Retrieval (ICMR)},
    year={2025}
}