Efficient dynamic algorithms for some geometric intersection problems

DOI10.1016/0020-0190(90)90151-MMaRDI QIDQ918702zbMATH OpenFDO

Authors Ravi Janardan, Siu-Wing Cheng

Publication date 1990

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

zbMATH Keywords

computational complexityanalysis of algorithmscomputational geometrydata structuresdesign of algorithms

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Dynamic orthogonal segment intersection search
• GENERALIZED INTERSECTION SEARCHING PROBLEMS
• Dynamic Point Location in General Subdivisions
• Fast dynamic intersection searching in a set of isothetic line segments
• Space searching for intersecting objects

Cites work

• scientific article; zbMATH DE number 3887061 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• Adding range restriction capability to dynamic data structures
• Binary Search Trees of Bounded Balance
• Dynamic orthogonal segment intersection search
• Filtering Search: A New Approach to Query-Answering
• Priority Search Trees
• Rectilinear line segment intersection, layered segment trees, and dynamization
• The design of dynamic data structures
• Worst-case optimal insertion and deletion methods for decomposable searching problems

Cited in

(17)

• Geometric algorithms for finding a point in the intersection of balls
• Space searching for intersecting objects
• Space searching for intersecting objects
• INTERSECTION PROBLEMS ON SEGMENTS UNDER BOUNDARY UPDATES WITH APPLICATION TO PERSISTENT LISTS
• Connected component and simple polygon intersection searching
• A bucketing algorithm for the orthogonal segment intersection search problem and its practical efficiency
• Dynamic rectangular intersection with priorities
• Dynamic orthogonal segment intersection search
• Further results on generalized intersection searching problems: Counting, reporting, and dynamization
• A unified approach to geometric problems using dual cone transformation:
• Fast dynamic intersection searching in a set of isothetic line segments
• RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
• Intersection Algorithms and CAGD
• Efficient non-intersection queries on aggregated geometric data
• An $O(E\log E + I)$ Expected Time Algorithm for the Planar Segment Intersection Problem
• A random direction algorithm for an intersection problem
• Efficient algorithms for line and curve segment intersection using restricted predicates

This page was built for publication: Efficient dynamic algorithms for some geometric intersection problems

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