Efficient structures for geometric data management (Q1188530)

The main emphasis of the book is to present suitable representation schemes for efficient geometric data manangement. A survey of common representation schemes is the start point of the book covering such schemes as boundary representation (B-rep), sweep operation, quadtrees and octrees and constructive solid geometry (CSG). Polyhedral chains are then introduced as a new representation scheme for polyhedral data in arbitrary dimensions. In particular, convex polyhedral chains are discussed and it is shown how to decompose set operations into two steps: the first is a collection vector operation and the second is a garbage collection where vectors representing empty cells are eliminated. In order to perform garbage collection efficiently, a dual approach to detect intersections of hyperplanes and convex polyhedra is considered. Geometric index structures are discussed to support search operators. The cell tree, a binary space partition tree, is designed to support paged memory in an attempt to minimize the number of page faults per search operation. A hierarchical data structure, the arc tree, is presented as an approximation scheme for free-form curves. An arc tree represents a curve of length L by a balanced binary tree such that any subtree whose root in on the k-th level represents a subcurve of length \(L/2^ k\). Based on this data structure, geometric interrogation algorithms, e.g., curve/curve intersection, are presented. In geometric computing, it is necessary to compute and store multiple representations of the given data in order to provide the most efficient representation available for every operator. The maintenance of multiple representations, however, brings about problems concerning their availability and mutual consistency.