Efficient 3D region guarding for multimedia data processing

With the advance of scanning devices, 3-d geometric models have been captured and widely used in animation, video, interactive virtual environment design nowadays. Their effective analysis, integration, and retrieval are important research topics in multimedia. This paper studies a geometric modeling problem called 3D region guarding. The 3D region guarding is a well known NP-hard problem; we present an efficient hierarchical integer linear programming (HILP) optimization algorithm to solve it on massive data sets. We show the effectiveness of our algorithm and briefly illustrate its applications in multimedia data processing and computer graphics such as shape analysis and retrieval, and morphing animation.