scientific article; zbMATH DE number 1241835

zbMath0916.68031MaRDI QIDQ4225298

Jeff Erickson, Pankaj K. Agarwal

Publication date: 18 January 1999

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

range-searching problem

Mathematics Subject Classification ID

Related Items (only showing first 100 items - show all)

Faster algorithms for largest empty rectangles and boxes ⋮ Higher order Delaunay triangulations ⋮ On the arrangement of stochastic lines in \(\mathbb{R}^2\) ⋮ Output sensitive algorithms for approximate incidences and their applications ⋮ Algorithms for graphs of bounded treewidth via orthogonal range searching ⋮ Computing minimum-area rectilinear convex hull and \(L\)-shape ⋮ Optimal external memory planar point enclosure ⋮ Efficient algorithms for counting and reporting pairwise intersections between convex polygons ⋮ Labeling a rectilinear map more efficiently ⋮ Triangular range counting query in 2D and its application in finding \(k\) nearest neighbors of a line segment ⋮ Lower bounds for intersection searching and fractional cascading in higher dimension ⋮ A semi-algebraic version of Zarankiewicz's problem ⋮ Finding Pairwise Intersections Inside a Query Range ⋮ Chromatic distribution of \(k\)-nearest neighbors of a line segment in a planar colored point set ⋮ On the Power of the Semi-Separated Pair Decomposition ⋮ A survey of mass partitions ⋮ The range 1 query (R1Q) problem ⋮ Range searching in multidimensional databases using navigation metadata ⋮ Bidding on Configurations in Internet Ad Auctions ⋮ Efficient Data Structures for the Orthogonal Range Successor Problem ⋮ Indexing text using the Ziv--Lempel trie ⋮ Finding pairwise intersections of rectangles in a query rectangle ⋮ On Ray Shooting for Triangles in 3-Space and Related Problems ⋮ Indexing for summary queries ⋮ New bounds for range closest-pair problems ⋮ Entropy-bounded representation of point grids ⋮ Subquadratic algorithms for succinct stable matching ⋮ Improved data structures for the orthogonal range successor problem ⋮ Indexing moving points ⋮ Time and space efficient collinearity indexing ⋮ On reverse shortest paths in geometric proximity graphs ⋮ Semi-algebraic Ramsey numbers ⋮ Half-plane point retrieval queries with independent and dependent geometric uncertainties ⋮ An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ³ ⋮ Two-dimensional substring indexing. ⋮ Throwing a sofa through the window ⋮ Rectangle stabbing and orthogonal range reporting lower bounds in moderate dimensions ⋮ Tight lower bounds for halfspace range searching ⋮ Optimal partition trees ⋮ A (\(1+{\varepsilon}\))-approximation algorithm for 2-line-center ⋮ Biased range trees ⋮ On bounded leg shortest paths problems ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Approximating the k-Level in Three-Dimensional Plane Arrangements ⋮ On the power of the semi-separated pair decomposition ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Bold graph drawings ⋮ Detecting Regular Visit Patterns ⋮ A faster algorithm for computing motorcycle graphs ⋮ Maintaining Extremal Points and Its Applications to Deciding Optimal Orientations ⋮ Property-preserving data reconstruction ⋮ Data structures for extension violations in a query range ⋮ Ray shooting and intersection searching amidst fat convex polyhedra in 3-space ⋮ Approximate range searching in higher dimension ⋮ Space efficient dynamic orthogonal range reporting ⋮ Visibility Testing and Counting ⋮ Range closest-pair search in higher dimensions ⋮ Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points ⋮ Searching for the closest-pair in a query translate ⋮ On approximate range counting and depth ⋮ Finding pairwise intersections inside a query range ⋮ Color-spanning localized query ⋮ Range search on tuples of points ⋮ Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D ⋮ On the number of regular vertices of the union of Jordan regions ⋮ Independent set of intersection graphs of convex objects in 2D ⋮ Approximate range searching using binary space partitions ⋮ Approximating nearest neighbor among triangles in convex position ⋮ On Euclidean vehicle routing with allocation ⋮ Approximate range searching: The absolute model ⋮ Cost prediction for ray shooting in octrees ⋮ Regular and non-regular point sets: Properties and reconstruction ⋮ Unnamed Item ⋮ The \(n\)-dimensional \(k\)-vector and its application to orthogonal range searching ⋮ Region-restricted clustering for geographic data mining ⋮ Efficient \(c\)-oriented range searching with DOP-trees ⋮ Approximate input sensitive algorithms for point pattern matching ⋮ Near-linear algorithms for geometric hitting sets and set covers ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Efficient Top-k Queries for Orthogonal Ranges ⋮ The effect of corners on the complexity of approximate range searching ⋮ Dynamic connectivity for axis-parallel rectangles ⋮ Unnamed Item ⋮ Cache-oblivious R-trees ⋮ On regular vertices of the union of planar convex objects ⋮ Stronger Tradeoffs for Orthogonal Range Querying in the Semigroup Model ⋮ Unnamed Item ⋮ Crossing patterns of semi-algebraic sets ⋮ Array Range Queries ⋮ Closest-pair queries in fat rectangles ⋮ New Bounds for Range Closest-Pair Problems ⋮ Approximate Range Queries for Clustering ⋮ Efficient searching with linear constraints ⋮ Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model ⋮ Geometric BWT: compressed text indexing via sparse suffixes and range searching ⋮ Reporting intersecting pairs of convex polytopes in two and three dimensions ⋮ On approximate nearest neighbors under \(l_\infty\) norm ⋮ Multilevel polynomial partitions and simplified range searching

This page was built for publication: