An algorithm for generalized point location and its applications
From MaRDI portal
Publication:2639635
DOI10.1016/S0747-7171(08)80065-XzbMath0718.68029MaRDI QIDQ2639635
Bernard Chazelle, Micha Sharir
Publication date: 1990
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
point location; multidimensional searching; logarithmic query time; Collins' classical quantifier elimination procedure; higher-dimensional space
68Q25: Analysis of algorithms and problem complexity
68P15: Database theory
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
Related Items
Peeling Potatoes Near-Optimally in Near-Linear Time, Efficient Algorithm for Computing the Triangle Maximizing the Length of Its Smallest Side Inside a Convex Polygon, Large \(k\)-gons in a 1.5D terrain, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, Algorithms for bichromatic line-segment problems and polyhedral terrains, Efficient randomized algorithms for some geometric optimization problems, Efficient evaluation of specific queries in constraint databases, Ray shooting on triangles in 3-space, Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
- Visibility and intersection problems in plane geometry
- Some dynamic computational geometry problems
- \(\epsilon\)-nets and simplex range queries
- Some techniques for geometric searching with implicit set representations
- New applications of random sampling in computational geometry
- An inequality for the discriminant of a polynomial
- On the computational power of pushdown automata
- A new decision method for elementary algebra
- Optimal Point Location in a Monotone Subdivision
- Searching and storing similar lists
- A linear algorithm for computing the visibility polygon from a point
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
- Multidimensional Searching Problems
- Cylindrical Algebraic Decomposition I: The Basic Algorithm
- Decision procedures for real and p‐adic fields
- On Euclid's Algorithm and the Theory of Subresultants
- On the Betti Numbers of Real Varieties
