Dynamic orthogonal segment intersection search

DOI10.1016/0196-6774(87)90024-1MaRDI QIDQ3783594zbMATH OpenOpenAlexFDO

Authors T. Asano, Hideki Imai

Publication date 1987

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

Full work available at URL https://doi.org/10.1016/0196-6774(87)90024-1

zbMATH Keywords

data structuresdynamic searchgeometric searchingorthogonal segment intersection searchset-splitting

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Efficient dynamic algorithms for some geometric intersection problems
• Connected component and simple polygon intersection searching
• Fast dynamic intersection searching in a set of isothetic line segments
• Dynamic Point Location in General Subdivisions
• GENERALIZED INTERSECTION SEARCHING PROBLEMS

Cited in

(31)

• Light orthogonal networks with constant geometric dilation
• Fast dynamic intersection searching in a set of isothetic line segments
• A bucketing algorithm for the orthogonal segment intersection search problem and its practical efficiency
• Output-sensitive generation of the perspective view of isothetic parallelepipeds
• Orthogonal queries in segments
• Edge-orders
• Union and split operations on dynamic trapezoidal maps
• Enhanced layered segment trees: a pragmatic data structure for real-time processing of geometric objects
• Connected component and simple polygon intersection searching
• Algorithmic aspects of proportional symbol maps
• An O(n+m) certifying triconnnectivity algorithm for Hamiltonian graphs
• Minimum-link paths revisited
• Rectilinear paths among rectilinear obstacles
• scientific article; zbMATH DE number 1691485 (Why is no real title available?)
• Mondshein sequences (a.k.a. (2,1)-orders)
• scientific article; zbMATH DE number 432982 (Why is no real title available?)
• Processing an offline insertion-query sequence with applications
• Dynamic rectangular intersection with priorities
• Direct dynamic structures for some line segment problems
• scientific article; zbMATH DE number 2079392 (Why is no real title available?)
• scientific article; zbMATH DE number 1555970 (Why is no real title available?)
• INTERSECTION PROBLEMS ON SEGMENTS UNDER BOUNDARY UPDATES WITH APPLICATION TO PERSISTENT LISTS
• Output-sensitive generation of the perspective view of isothetic parallelepipeds
• A linear algorithm for the maximal planar subgraph problem
• Point Location in Incremental Planar Subdivisions.
• Fast incremental planarity testing
• An efficient direct approach for computing shortest rectilinear paths among obstacles in a two-layer interconnection model
• Incremental hive graph
• Linear time online algorithms for constructing linear-size suffix trie
• Dynamic fractional cascading
• Efficient dynamic algorithms for some geometric intersection problems

This page was built for publication: Dynamic orthogonal segment intersection search

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