The Taub Faculty of Computer Science Events and Talks

In digital geometry, Euclidean objects are represented by their discrete approximations e.g., subsets of the lattice of integers. Rigid motions of such sets have to be defined as maps from and onto a given discrete space. One way to design such motions is to combine continuous rigid motions defined on Euclidean space with a digitization operator. However, digitized rigid motions often no longer satisfy properties of their continuous siblings. Indeed, due to digitization, such transformations do not preserve distances, furthermore bijectivity and point connectivity are generally lost.

In the context of digitized rigid motions on the 3D integer lattice we first focus on the open problem of determining whether a 3D digitized rotation is bijective. In our approach, we explore arithmetic properties of Lipschitz quaternions. This leads to an algorithm which answers the question whether a given digitized rotation—related to a Lipschitz quaternion—is bijective. Finally, we study at a local scale geometric and topological defects induced by digitized rigid motions. Such an analysis consists of generating all the images of a finite digital set under digitized rigid motions. This problem amounts to computing an arrangement of hypersurfaces in a 6D parameter space. The dimensionality makes the problem practically unsolvable for state-of-the-art techniques such as cylindrical algebraic decomposition. We propose an ad hoc solution, which mainly relies on parameter uncoupling, and an algorithm for computing sample points of 3D connected components in an arrangement of second degree polynomials.