Rectilinear line segment intersection, layered segment trees, and dynamization

DOI10.1016/0196-6774(82)90016-5MaRDI QIDQ3939249zbMATH OpenOpenAlexFDO

Authors Vijay K. Vaishnavi, D. Wood

Publication date 1982

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(82)90016-5

zbMATH Keywords

data structurerectangle intersectionsearching

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Information storage and retrieval of data (68P20) Discrete mathematics in relation to computer science (68R99)

Cited in

(19)

• Interval graphs and related topics
• Fast dynamic intersection searching in a set of isothetic line segments
• On some union and intersection problems for polygons with fixed orientations
• Fractional cascading. I: A data structuring technique
• A bucketing algorithm for the orthogonal segment intersection search problem and its practical efficiency
• General methods for 'all elements' and 'all pairs' problems
• Polygonal intersection searching
• On the equivalence of some rectangle problems
• On the optimal binary plane partition for sets of isothetic rectangles
• Algorithms for bichromatic line-segment problems and polyhedral terrains
• The range co-minima problem
• Enhanced layered segment trees: a pragmatic data structure for real-time processing of geometric objects
• Shortest paths among transient obstacles
• A worst-case efficient algorithm for hidden-line elimination^†
• External-memory algorithms for processing line segments in geographic information systems
• Convexity helps iterated search in 3D
• An O(n log n) Manhattan path algorithm
• Dynamic fractional cascading
• Efficient dynamic algorithms for some geometric intersection problems

This page was built for publication: Rectilinear line segment intersection, layered segment trees, and dynamization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3939249)