Efficiently Computing And Representing Aspect Graphs Of Polyhedral Objects

The aspect graph is one of the approaches to representing of 3-D shape for the purposes of object recognition. In this approach, the viewing space of an object is partitioned into regions, such that in each region the topology of the line drawing of the object does not change. The viewing data of an object is the partition of the viewing space together with a representative view in each region, We present an efficient algorithm for computing the viewing data for line drawings of polyhedral objects under orthographic projection. For an object of size O(n) whose partition of size O(m), the algorithm runs O(n4 log n t m log m) time. Using a novel data structure, we construct the set of all views in optimal O(m) time and space.