Overlaying surface meshes, part I: Algorithms

We describe an efficient and robust algorithm for computing a common refinement of two meshes modeling the same surface of arbitrary shape by overlaying them on top of each other. A common refinement is an important data structure for transferring data between meshes that have different combinatorial structures. Our algorithm is optimal in time and space, with linear complexity, and is robust even with inexact computations, through the techniques of error analysis, detection of topological inconsistencies, and automatic resolution of such inconsistencies. We present the verification and some further enhancement of robustness in Part II.