# Computer Science News

## CS research wins best paper award

A paper by Nicolas Mellado and Niloy J. Mitra (of UCL-CS) and Dror Aiger (Google Inc.) has won "Best Paper" award at the Symposium on Geometry Processing, a premier venue for Geometry Processing.

The paper describes Super4PCS, an algorithm for the fast global registration of point-clouds via smart indexing.

This work has been developed in the context of large-scale scene acquisition, to register pairs of point-clouds in the same 3D frame by estimating their relative rotation and translation. Common approaches such as the Iterative Closest Point (ICP) algorithm requires input pose, while the state-of-the-art global registration algorithms (eg. 4-Points Congruent Sets algorithm by Dror Aiger, Niloy J. Mitra and Daniel Cohen-Or) are slow to run when there are many data points.

The Super4PCS algorithm developed by the team is optimal, i.e., runs in linear time on any number of data points. It is also output sensitive in the complexity of the alignment problem based on the (unknown) overlap across scan pairs, and does not require an initial pose between them. This results in significant speed-up over alternative approaches and allows unstructured efficient acquisition of scenes at scales previously not possible.