Abstract :
In two dimensions, the beta-skeleton is one of the most practical methods for reconstructing smooth curves from a given unorganized point set because of its provable guarantee. In three dimensions, however, the beta-skeleton cannot be used for surface reconstruction because it may contain unwanted holes omnipresently, no matter how high sampling density is. To overcome this difficulty, an extension of the beta-skeleton, called greedy beta-skeleton, is proposed. It is shown by computational experiments that the unwanted holes do not appear in the greedy beta-skeleton even when the dimension is three. In addition, the greedy beta-skeletons are computed for several practical inputs, and their fairness is examined. Computation results for some variants of the greedy beta-skeleton are also reported.
Keywords :
greedy algorithms; image reconstruction; surface reconstruction; greedy beta-skeleton; smooth curve reconstruction; surface reconstruction; unorganized point set; Cities and towns; Computer science; Computer vision; Greedy algorithms; Image reconstruction; Piecewise linear approximation; Sampling methods; Skeleton; Surface reconstruction; Topology;
