Delaunay based shape reconstruction from large data

Surface reconstruction provides a powerful paradigm for modeling shapes from samples. For point cloud data with only geometric coordinates as input, Delaunay based surface reconstruction algorithms are shown to be quite effective both in theory and practice. However, a major complaint against Delaunay based methods is that they are slow and cannot handle large data. We extend the COCONE algorithm to handle supersize data. This is the first reported Delaunay based surface reconstruction algorithm that can handle data containing more than a million sample points on a modest machine.