Linear space data structures for two types of range search

DOI10.1007/BF02187875MaRDI QIDQ578916zbMATH OpenFDO

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

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)

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

Cites work

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

Cited in

(12)

• Linear space adaptive data structures for planar range reporting
• 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

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)