Fast dynamic intersection searching in a set of isothetic line segments

DOI10.1016/0020-0190(85)90054-7MaRDI QIDQ1065550zbMATH OpenOpenAlexFDO

Authors Ralf Hartmut Gueting

Publication date 1985

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(85)90054-7

zbMATH Keywords

computational geometryhalfobject techniqueline segment intersection searchingrange treesegment tree

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Recommendations

• Efficient dynamic algorithms for some geometric intersection problems
• Dynamic orthogonal segment intersection search
• An optimal algorithm for intersecting line segments in the plane
• Efficient algorithms for line and curve segment intersection using restricted predicates
• Segment intersection searching problems in general settings
• Segment intersection searching problems in general settings
• scientific article; zbMATH DE number 2079392
• Fast detection of polyhedral intersection
• Dynamic C-oriented polygonal intersection searching
• On intersection searching problems involving curved objects

Cites work

• A new approach to rectangle intersections part I
• Counting and Reporting Intersections of d-Ranges
• Decomposable searching problems
• scientific article; zbMATH DE number 3995096 (Why is no real title available?)
• Optimal algorithms to compute the closure of a set of iso-rectangles
• Priority Search Trees
• Rectilinear line segment intersection, layered segment trees, and dynamization
• Some methods of computational geometry applied to computer graphics

Cited in

(9)

• A bucketing algorithm for the orthogonal segment intersection search problem and its practical efficiency
• Searching for segments with largest relative overlap
• Efficient algorithms for line and curve segment intersection using restricted predicates
• An efficient method to evaluate intersections on big data sets
• Direct dynamic structures for some line segment problems
• Dynamic orthogonal segment intersection search
• INTERSECTION PROBLEMS ON SEGMENTS UNDER BOUNDARY UPDATES WITH APPLICATION TO PERSISTENT LISTS
• Dynamic fractional cascading
• Efficient dynamic algorithms for some geometric intersection problems

This page was built for publication: Fast dynamic intersection searching in a set of isothetic line segments

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