Quasi-optimal upper bounds for simplex range searching and new zone theorems
From MaRDI portal
Publication:1201746
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
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
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
