Fitting polygonal regions for matching 3D polyhedra

Matching geometric objects is a fundamental problem in computational geometry with applications in many other areas, such as computer vision, biology, and archaelogy. In this paper, we study an important partial matching problem motivated from applications in several such areas. The input is in the form of sets of under-sampled slices of one (or more) unknown 3D objects, possibly generated by slicing planes of arbitrary orientations, the question we are interested in is whether it is 'possible' that two under-sampled sets have been taken from the same object. Alternatively, can we determine with 'certainty' that the given input samples cannot be from the same object. We present efficient algorithms for addressing these questions. Our algorithms are based on interesting geometric techniques and enables answering these queries either as plausible or a certain negative.