Algorithmic aspects of alternating sum of volumes. Part 1: Data structure and difference operation

Abstract

In terms of basic theory, a unique conversion from a boundary representation to a CSG representation is of importance. In terms of application, the extraction of features by convex decomposition is of interest. The alternating sum of volumes (ASV) technique offers both. However, some algorithmic issues are still unresolved. The paper is the first section of a 2-part paper that addresses specialized set operations and the convergence of the ASV process. In the first part, a fast difference operation for the ASV process and a data structure for pseudopolyhedra are introduced.A fast difference operation between an object and its convex hull is made possible by the crucial observation it takes only linear time to distinguish them. However, it takes O(NlogN) time to construct a data structure with the proper tags. The data structure supporting the operation is a pseudopolyhedron, capturing the special relationship between an object and its convex hull. That the data structure is linear in space is also shown.