Halfplanar range search in linear space and \(O(n^{0.695})\) query time
From MaRDI portal
Publication:1097038
DOI10.1016/0020-0190(86)90088-8zbMath0634.68064OpenAlexW2064098750WikidataQ54309897 ScholiaQ54309897MaRDI QIDQ1097038
Herbert Edelsbrunner, Ermo Welzl
Publication date: 1986
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(86)90088-8
computational geometryconjugation treehalfplanar range queryham-sandwich treeworst-case time analysis
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Other problems of combinatorial convexity (52A37)
Related Items
The power of geometric duality, Algorithms for projecting points to give the most uniform distribution with applications to hashing, Triangular range counting query in 2D and its application in finding \(k\) nearest neighbors of a line segment, \(\epsilon\)-nets and simplex range queries, Fractional cascading. II: Applications, TWO-DIMENSIONAL RANGE SEARCH BASED ON THE VORONOI DIAGRAM, Simplex range reporting on a pointer machine, Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems, Half-plane point retrieval queries with independent and dependent geometric uncertainties, Epsilon-nets for halfplanes, 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, On counting pairs of intersecting segments and off-line triangle range searching, A Real Elementary Approach to the Master Recurrence and Generalizations, Intersection queries in sets of disks, How hard is half-space range searching?, Efficient partition trees, Quasi-optimal upper bounds for simplex range searching and new zone theorems, Dynamic partition trees, Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses, Lower Bounds on the Complexity of Polytope Range Searching, Intersection queries in sets of disks, Linear space data structures for two types of range search, The complexity and construction of many faces in arrangements of lines and of segments, Spanning trees with low crossing number, Lower bounds on the complexity of simplex range reporting on a pointer machine, Implicitly representing arrangements of lines or segments, The intersection searching problem for c-oriented polygons, Reporting and counting segment intersections, Quasi-optimal range searching in spaces of finite VC-dimension, Optimal solutions for a class of point retrieval problems, Dynamic partition trees, The power of geometric duality revisited
Cites Work
- Worst-case optimal insertion and deletion methods for decomposable searching problems
- Polygonal intersection searching
- Quad trees: A data structure for retrieval by composite keys
- Neighbor finding techniques for images represented by quadtrees
- Partitioning with two lines in the plane
- Polygon Retrieval
- Multidimensional binary search trees used for associative searching
- Constructing Belts in Two-Dimensional Arrangements with Applications
- Unnamed Item
- Unnamed Item
