×

Direct dynamic structures for some line segment problems. (English) Zbl 0585.68065

Summary: Simple direct dynamic binary tree structures for two line segment problems are introduced. Both structures provide for O(log n) updating and querying and can be based on any balanced class of binary search trees, for example, AVL trees. The measure tree solves a nondecomposable searching problem, while the stabbing tree improves the known updating and querying time for its corresponding application.

MSC:

68P10 Searching and sorting
PDF BibTeX XML Cite
Full Text: DOI