Combinatorial curve reconstruction in Hilbert spaces: A new sampling theory and an old result revisited

摘要

The goals of this paper are twofold. The first is to present a new sampling theory for curves, based on a new notion of local feature size. The properties of this new feature size are investigated, and are compared with the standard feature size definitions. The second goal is to revisit an existing algorithm for combinatorial curve reconstruction in spaces of arbitrary dimension, the Nearest Neighbour Crust of Dey and Kumar [Proc. ACM-SIAM Sympos. Discrete Algorithms, 1999, pp. 893-894], and to prove its validity under the new sampling conditions. Because the new sampling theory can imply less dense sampling, the new proof is, in some cases, stronger than that presented in [Proc. ACM-SIAM Sympos. Discrete Algorithms, 1999, pp. 893-894]. Also of interest are the techniques used to prove the theorem, as they are unlike those used used in the curve reconstruction literature to date.