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 locationmultidimensional searchinglogarithmic query timeCollins' classical quantifier elimination procedurehigher-dimensional space
Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items
Ray shooting on triangles in 3-space, Peeling Potatoes Near-Optimally in Near-Linear Time, Large \(k\)-gons in a 1.5D terrain, Efficient evaluation of specific queries in constraint databases, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time., Efficient randomized algorithms for some geometric optimization problems, Efficient Algorithm for Computing the Triangle Maximizing the Length of Its Smallest Side Inside a Convex Polygon, Algorithms for bichromatic line-segment problems and polyhedral terrains
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
