Abstract

Geometric congruence asks whether two point multisets are identical up to translation and rotation. This problem is a fundamental building block for many computer vision applications. To investigate the space efficiency aspect of this problem, we study geometric congruence in the streaming model with finite-precision rational inputs. In contrast to the conventional algorithmic setting, the input coordinates are rational numbers of bounded bit length presented in a stream with limited access, and the goal is to solve the problem using as little memory as possible. Our main algorithmic results are two randomized algorithms for 2D congruence testing that use polylogarithmic space and three passes. To achieve this exceptional space efficiency, we employ several number-theoretic approaches to compress the relevant high-precision information into moderate-precision statistics. On the hardness side, we use communication complexity methods to establish a matching space lower bound. Moreover, for another natural variant, approximate congruence testing, we show that no low-pass streaming algorithm can solve the problem without using linear space, thus establishing a gap between exact and approximate congruence testing in the streaming model.

All faculty and students are welcome to join.