In the pose-estimation problem we need to rotate a set of n points (e.g. markers, visual features, or stars in the sky) and choose one of their n! permutations, so that the sum of squared corresponding distances to another ordered set of n markers is minimized. 

 

We prove that every set has a weighted subset (core-set) of size independent of n, such that computing the optimal orientation of the small core-set would yield exactly the same result as using the full set of n points. This set can be computed using the  Caratheodory Theorem from computational geometry. A smaller approximated core-set with applications to game theory, streaming k-means and PCA is also suggested.

 

I will show how my group used this algorithm to develop a low-cost real-time tracking system that turns a toy drone into an autonomous quadcopter.