This paper provides a theoretical analysis of the minimum number of camera viewpoints required to guarantee correct verification of spatial relations with high probability. It establishes information-theoretic lower bounds on sampling complexity, introduces a PAC-learning framework, and presents upper bounds for sampling strategies.
Key findings
Formal characterization of sampling complexity in terms of visibility coverage number and relation complexity.
Upper bounds for uniform and adaptive sampling strategies.
A constructive algorithm achieving near-optimal sample complexity.
Theoretical guarantees for verification correctness under bounded noise.
Limitations & open questions
Does not address practical implementation challenges in real-world scenarios.
Assumes bounded observation noise, which may not always be the case.