Polygon Retrieval
From MaRDI portal
Publication:3936209
DOI10.1137/0211012zbMath0478.68060OpenAlexW4244897565MaRDI QIDQ3936209
Publication date: 1982
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0211012
searchingworst-case execution timedata structurerange treequad treeaugmented treemultidimensional retrievalsuper B-tree
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Data structures (68P05) Information storage and retrieval of data (68P20)
Related Items
Diameter partitioning, On range searching with semialgebraic sets, Algorithms for ham-sandwich cuts, The power of geometric duality, Partitioning point sets in arbitrary dimension, \(\epsilon\)-nets and simplex range queries, Computing a ham-sandwich cut in two dimensions, Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem, Halfplanar range search in linear space and \(O(n^{0.695})\) query time, FITTING A STEP FUNCTION TO A POINT SET WITH OUTLIERS BASED ON SIMPLICIAL THICKNESS DATA STRUCTURES, Topology and combinatorics of partitions of masses by hyperplanes, A survey of mass partitions, Equipartition of mass distributions by hyperplanes, Simplex range reporting on a pointer machine, Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems, Topology of the Grünbaum–Hadwiger–Ramos hyperplane mass partition problem, Half-plane point retrieval queries with independent and dependent geometric uncertainties, Tight lower bounds for halfspace range searching, Optimal partition trees, Simplex Range Searching and Its Variants: A Review, Unnamed Item, Storing line segments in partition trees, Improved Points Approximation Algorithms Based on Simplicial Thickness Data Structures, Separating collections of points in Euclidean spaces, On counting pairs of intersecting segments and off-line triangle range searching, Reporting points in halfspaces, How hard is half-space range searching?, Efficient partition trees, Quasi-optimal upper bounds for simplex range searching and new zone theorems, An equipartition of planar sets, Dynamic partition trees, Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses, Conical equipartitions of mass distributions, Lower Bounds on the Complexity of Polytope Range Searching, On a problem about quadrant-depth, Linear space data structures for two types of range search, Lower bounds on the complexity of simplex range reporting on a pointer machine, Implicitly representing arrangements of lines or segments, Points with large \(\alpha \)-depth, New applications of random sampling in computational geometry, On the number of line separations of a finite set in the plane, On range searching with semialgebraic sets, Quasi-optimal range searching in spaces of finite VC-dimension, New trie data structures which support very fast search operations, Efficient searching with linear constraints, Non-partitionable point sets, Approximate range searching, Dynamic partition trees, The power of geometric duality revisited, IMPROVED POINTER MACHINE AND I/O LOWER BOUNDS FOR SIMPLEX RANGE REPORTING AND RELATED PROBLEMS
