On Sampling and Reconstructing Surfaces with Boundaries

Surface reconstruction algorithms can ensure correctness of the reconstructed surface by imposing conditions on sampling and by assuming that the given point set satisfies the prescribed conditions. Traditionally, such sampling conditions impose minimum required sampling density for correct reconstruction. Let us assume that no additional information is provided to the reconstruction algorithm other than the input set of points. Under this assumption, we show that imposing minimum required sampling density is not sufficient to ensure correct reconstruction of surfaces with boundaries. In other words, to prove the correctness of the reconstructed surface, either the sampling conditions have to be strengthened or more information has to be provided to the reconstruction algorithm. Further, we prove that the strengthened sampling condition for sampling surfaces with boundaries has a unique property called non-monotonicity. We analyze the applicability of this framework to various algorithms like medial axis estimation algorithms, curve reconstruction algorithms, and reconstruction of surfaces from noisy point sets