Linear space data structures for two types of range search

DOI10.1007/BF02187875zbMATH Open0624.68054MaRDI QIDQ578916FDOQ578916

Authors: Bernard Chazelle, Herbert Edelsbrunner 

Publication date: 1987

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131014

Recommendations

• Orthogonal range searching in linear and almost-linear space
• Line arrangements and range search
• Algorithms for three-dimensional dominance searching in linear space.
• Orthogonal Range Searching in Linear and Almost-Linear Space
• Efficient data structures for range searching on a grid

zbMATH Keywords

computational geometryrange searchingdomination searchinghomothetic range search problemlinear space data structures

Mathematics Subject Classification ID

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

Cites Work

• Multidimensional divide-and-conquer
• Applications of a Planar Separator Theorem
• Filtering Search: A New Approach to Query-Answering
• The power of geometric duality
• On Finding the Maxima of a Set of Vectors
• Optimal Search in Planar Subdivisions
• Priority Search Trees
• Optimal Point Location in a Monotone Subdivision
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Fractional cascading. I: A data structuring technique
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• Polygon Retrieval
• Finding the intersection of two convex polyhedra
• Optimal solutions for a class of point retrieval problems

Cited In (12)

• An application of $m$-ary trees to the design of data structures for geometric searching problems
• Point enclosure problem for homothetic polygons
• The intersection searching problem for c-oriented polygons
• On space efficient two dimensional range minimum data structures
• An efficient algorithm for the 1D total visibility-index problem and its parallelization
• Algorithms for three-dimensional dominance searching in linear space.
• Features of solving the range searching problems for d-dimensional case
• Space Efficient Multi-dimensional Range Reporting
• On Dominance Reporting in 3D
• Fractional cascading. II: Applications
• Incremental hive graph
• Linear space adaptive data structures for planar range reporting

This page was built for publication: Linear space data structures for two types of range search

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