Quasi-optimal upper bounds for simplex range searching and new zone theorems

DOI10.1007/BF01758854zbMath0788.68141OpenAlexW2067695105WikidataQ54309635 ScholiaQ54309635MaRDI QIDQ1201746

Bernard Chazelle, Micha Sharir, Ermo Welzl

Publication date: 17 January 1993

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01758854

zbMATH Keywords

complexitycomputational geometryrange searching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (36)

Iterated nearest neighbors and finding minimal polytopes ⋮ On range searching with semialgebraic sets ⋮ Efficient ray shooting and hidden surface removal ⋮ Ray shooting on triangles in 3-space ⋮ Efficient algorithms for counting and reporting pairwise intersections between convex polygons ⋮ Triangular range counting query in 2D and its application in finding \(k\) nearest neighbors of a line segment ⋮ Dynamic half-space range reporting and its applications ⋮ IMPROVED ALGORITHMS FOR THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE 3-TREES ⋮ Chromatic distribution of \(k\)-nearest neighbors of a line segment in a planar colored point set ⋮ Orthogonal queries in segments ⋮ 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects ⋮ Computing depth orders for fat objects and related problems ⋮ Simplex range reporting on a pointer machine ⋮ Point location in zones of \(k\)-flats in arrangements ⋮ Connected component and simple polygon intersection searching ⋮ Embedding Plane 3-Trees in ℝ2 and ℝ3 ⋮ Tight lower bounds for halfspace range searching ⋮ Optimal partition trees ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Relative convex hulls in semi-dynamic arrangements ⋮ Improved Points Approximation Algorithms Based on Simplicial Thickness Data Structures ⋮ On counting pairs of intersecting segments and off-line triangle range searching ⋮ Applications of a new space-partitioning technique ⋮ How hard is half-space range searching? ⋮ Range searching with efficient hierarchical cuttings ⋮ On ray shooting in convex polytopes ⋮ Efficient partition trees ⋮ Ray shooting and stone throwing with near-linear storage ⋮ ON ENUMERATING AND SELECTING DISTANCES ⋮ Lower bounds on the complexity of simplex range reporting on a pointer machine ⋮ Planar point sets determine many pairwise crossing segments ⋮ New lower bounds for Hopcroft's problem ⋮ On range searching with semialgebraic sets ⋮ Plane 3-Trees: Embeddability and Approximation ⋮ Weak visibility counting in simple polygons ⋮ IMPROVED POINTER MACHINE AND I/O LOWER BOUNDS FOR SIMPLEX RANGE REPORTING AND RELATED PROBLEMS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity and construction of many faces in arrangements of lines and of segments
• A deterministic view of random sampling and its use in geometry
• The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
• Triangulating a nonconvex polytope
• Combinatorial complexity bounds for arrangements of curves and spheres
• The upper envelope of piecewise linear functions: Tight bounds on the number of faces
• The upper envelope of piecewise linear functions: Algorithms and applications
• Partitioning arrangements of lines. II: Applications
• \(\epsilon\)-nets and simplex range queries
• Computing convolutions by reciprocal search
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• Separating two simple polygons by a sequence of translations
• Cutting hyperplane arrangements
• A singly exponential stratification scheme for real semi-algebraic varieties and its applications
• Efficient partition trees
• Implicitly representing arrangements of lines or segments
• Point location among hyperplanes and unidirectional ray-shooting
• New applications of random sampling in computational geometry
• Applications of random sampling in computational geometry. II
• Quasi-optimal range searching in spaces of finite VC-dimension
• Triangles in space or building (and analyzing) castles in the air
• Lower Bounds on the Complexity of Polytope Range Searching
• Geometric retrieval problems
• Searching and storing similar lists
• Point retrieval for polygons
• A Randomized Algorithm for Closest-Point Queries
• Polygon Retrieval

This page was built for publication: Quasi-optimal upper bounds for simplex range searching and new zone theorems