×

Enhanced layered segment trees: a pragmatic data structure for real-time processing of geometric objects. (English) Zbl 1006.68897

Summary: 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.

MSC:

68U99 Computing methodologies and applications
68T10 Pattern recognition, speech recognition
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Mehlhorn, K., Data Structures and Algorithms 3: Multidimensional Searching and Computational Geometry (1984), Springer: Springer Germany
[2] Samet, H., The Design and Analysis of Spatial Data Structures (1989), Addison-Wesley: Addison-Wesley Reading, MA
[3] Preparata, F. P.; Shamos, M. I., Computational Geometry (1985), Springer: Springer New York · Zbl 0759.68037
[4] J.L. Bentley, Algorithms for klee’s rectangle problems, Department of Computer Science, Carnegie Mellon University, 1977.; J.L. Bentley, Algorithms for klee’s rectangle problems, Department of Computer Science, Carnegie Mellon University, 1977.
[5] van Leeuwen, J.; Wood, D., The measure problem for rectangular ranges in \(d\)-space, J. Algorithms, 2, 282-300 (1981) · Zbl 0487.68032
[6] T.M. Kur, H. Kutluca, C. Aykanat, Blent zg, A comparison of spatial subdivision algorithms for sort-first rendering. in: Proceedings of the High Performance Computing and Networking, Lecture Notes in Computer Science, Springer, Berlin, 1997.; T.M. Kur, H. Kutluca, C. Aykanat, Blent zg, A comparison of spatial subdivision algorithms for sort-first rendering. in: Proceedings of the High Performance Computing and Networking, Lecture Notes in Computer Science, Springer, Berlin, 1997.
[7] University of Texas, Scientific animation, ccv image gallery, Internet Web Page, March 1999, URL:(http://www.ticam.utexas.edu/CCV/gallery/gallery.html; University of Texas, Scientific animation, ccv image gallery, Internet Web Page, March 1999, URL:(http://www.ticam.utexas.edu/CCV/gallery/gallery.html
[8] D.F. DeMenthon, Fractional cascading simplified, in: Proceedings of the Image Understanding Workshop, Washington, D.C., April 1993, pp. 653-659.; D.F. DeMenthon, Fractional cascading simplified, in: Proceedings of the Image Understanding Workshop, Washington, D.C., April 1993, pp. 653-659.
[9] Dima, C.; Parent, G.; Briggs, A.; Dickerson, M., Experimental analysis of polygon placement problems: an undergraduate research project in computational geometry, J. Comput. Small Colleges, 13, 5, 13-24 (1998)
[10] R.H. Güting, Fast dynamic line segment intersection searching, Report 87, Forschungsberichte Fachber. Inform., Univ. Dortmund, Dortmund, West Germany, 1984.; R.H. Güting, Fast dynamic line segment intersection searching, Report 87, Forschungsberichte Fachber. Inform., Univ. Dortmund, Dortmund, West Germany, 1984.
[11] D.L. Souvaine, I. Bjorling-Sachs, The contour problem for restricted-orientation polygons, Report LCSR-TR-137, Lab. Comput. Sci. Res., Rutgers Univ., New Brunswick, NJ, 1989.; D.L. Souvaine, I. Bjorling-Sachs, The contour problem for restricted-orientation polygons, Report LCSR-TR-137, Lab. Comput. Sci. Res., Rutgers Univ., New Brunswick, NJ, 1989. · Zbl 0815.68056
[12] Asano, Ta, Dynamic programming on intervals, Internat. J. Comput. Geom. Appl., 3, 323-330 (1993) · Zbl 0804.90130
[13] L. Arge, Efficient External-Memory Data Structures and Applications, PhD Thesis, University of Aarhus, Denmark, August 1996.; L. Arge, Efficient External-Memory Data Structures and Applications, PhD Thesis, University of Aarhus, Denmark, August 1996. · Zbl 0945.68191
[14] D. Sosna, Document version management using an adapted segment tree, Technical Report 9, Institute of Computer Science, University of Liepzig, 1997.; D. Sosna, Document version management using an adapted segment tree, Technical Report 9, Institute of Computer Science, University of Liepzig, 1997.
[15] Van Kreveld, M. J.; Overmars, M. H., Union-copy structures and dynamic segment trees, J. ACM, 40, 3, 635-652 (1993) · Zbl 0785.68018
[16] Vaishnavi, V. K.; Wood, D., Rectilinear line segment intersection, layered segment trees and dynamization, J. Algorithms, 3, 160-176 (1982) · Zbl 0481.68062
[17] Lee, D. T., Visibility of a simple polygon, Comput. Vision, Graphics Image Process., 5, 207-221 (1983) · Zbl 0532.68071
[18] Oommen, B. J.; Kashyap, R. L., A formal theory for optimal and information theoretic syntactic pattern recognition, Pattern Recognition, 31, 1159-1177 (1998)
[19] Oommen, B. J.; Zhang, K.; Lee, W., Numeric similarity and dissimilarity measures between two trees, IEEE Trans. Comput., TC-45, 1426-1434 (1996) · Zbl 1057.68650
[20] D. Willard, New data structures for orthogonal queries, Technical Report 22, Harvard University, 1978.; D. Willard, New data structures for orthogonal queries, Technical Report 22, Harvard University, 1978. · Zbl 0564.68071
[21] Chazelle and L. J. Guibas, B., Fractional cascading: I. a data structuring technique, Algorithmica, 1, 133-162 (1986) · Zbl 0639.68056
[22] S. Sen, Fractional cascading simplified, in: Proceedings of the Third Scandinavian Workshop Algorithm Theory, Lecture Notes in Computer Science, Vol. 621, Springer, Berlin, 1992, pp. 212-220.; S. Sen, Fractional cascading simplified, in: Proceedings of the Third Scandinavian Workshop Algorithm Theory, Lecture Notes in Computer Science, Vol. 621, Springer, Berlin, 1992, pp. 212-220.
[23] Mehlhorn, K.; Näher, S., Dynamic fractional cascading, Algorithmica, 5, 215-241 (1990) · Zbl 0693.68038
[24] V. Racherla, Parallelization and concurrent access of dynamic segment trees based on 2-3 trees, Master’s Thesis, School of Computer Science, University of Oklahoma, Norman, OK, USA, 1995.; V. Racherla, Parallelization and concurrent access of dynamic segment trees based on 2-3 trees, Master’s Thesis, School of Computer Science, University of Oklahoma, Norman, OK, USA, 1995.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.