A constant expected time, linear storage data structure for representing three-dimensional objects

Abstract

The interrogation of spatial relations and properties of three-dimensional objects are often involved in applications programs for CAD/CADM and robotics. These interrogations can be expressed in terms of low-level data retrieval queries called access primitives (APs). A data structure is presented for storing spatial relations of three-dimensional objects such that the amount of storage is linearly proportional to the number of entities, and the response time for the APs is constant on the average. Linear storage for this data structure is the lower bound. The data structure is in the form of a symmetric graph. Using <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">E</i> , the total number of edges of the object, as the unit, it is shown that the storage requirement of the symmetric data structure is 6 <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">E</i> . By defining nine general data structure accessing primitives, it is shown that any local topological query can be answered in constant time, on the average.