Enhanced layered segment trees: a pragmatic data structure for real-time processing of geometric objects

摘要

The data structure that is probably most used in the pattern recognition and image processing of geometric objects is the segment tree and its optimized variant, the “layered segment tree”. In all the versions currently known, except the work of Vaishnavi and Wood described later, these data structures do not operate in real time. Even in the latter scheme, although the structure can be implemented in real time and in an on-line fashion, the operation of insertion involves the sorting of the representations of the line segments in the tree. In essence, for all the reported algorithms, there is no known strategy to insert the segments one by one, other than the trivial strategy of processing them all together as in a batched-mode. In this paper, we present a strategy in which all the operations done on the tree can be done efficiently. Indeed, by improving the bottleneck, we prove that an arbitrary horizontal segment can be inserted into this data structure without invoking an expensive sorting process. We show that while this is accomplished by maintaining the same space and query complexity of the best-known algorithm, the version presented here is applicable to on-line real-time processing of line segments. The paper thus has applications in all areas of pattern recognition and image processing involving geometric objects.