Linear space data structures for two types of range search

DOI10.1007/BF02187875zbMath0624.68054MaRDI QIDQ578916

Herbert Edelsbrunner, Bernard Chazelle

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 searchinglinear space data structuresdomination searchinghomothetic range search problem

Mathematics Subject Classification ID

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

Related Items

Fractional cascading. II: Applications, An Efficient Algorithm for the 1D Total Visibility-Index Problem and Its Parallelization, Space Efficient Multi-dimensional Range Reporting, Incremental hive graph, Point enclosure problem for homothetic polygons, On Dominance Reporting in 3D, The intersection searching problem for c-oriented polygons, An application of $m$-ary trees to the design of data structures for geometric searching problems, Algorithms for three-dimensional dominance searching in linear space.

Cites Work

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