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 in [8], these structures do not operate in real time. Even in the best known scheme [8], although the structure can be implemented in real time and in an on-line fashion, the operation of “insertion” involves the sorting of the data 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 by which all the operations done on the tree can be done efficiently, Indeed, by improving the bottle-neck, 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.

Additional Metadata
Keywords Layered segment trees, Pattern recognition of geometric objects, Segment trees
Series Lecture Notes in Computer Science
Racherla, G. (Gopal), Radhakrishnan, S. (Sridhar), & Oommen, J. (2001). A new geometric tool for pattern recognition - An algorithm for real time insertion of layered segment trees. In Lecture Notes in Computer Science.