An algorithm for generalized point location and its applications
DOI10.1016/S0747-7171(08)80065-XzbMATH Open0718.68029MaRDI QIDQ2639635FDOQ2639635
Authors: Bernard Chazelle, Micha Sharir 
Publication date: 1990
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
Recommendations
point locationmultidimensional searchinglogarithmic query timeCollins' classical quantifier elimination procedurehigher-dimensional space
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Database theory (68P15)
Cites Work
- \(\epsilon\)-nets and simplex range queries
- New applications of random sampling in computational geometry
- Title not available (Why is that?)
- On the Betti Numbers of Real Varieties
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the computational power of pushdown automata
- A new decision method for elementary algebra
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
- Title not available (Why is that?)
- An inequality for the discriminant of a polynomial
- Optimal Point Location in a Monotone Subdivision
- Visibility and intersection problems in plane geometry
- Some dynamic computational geometry problems
- On Euclid's Algorithm and the Theory of Subresultants
- Multidimensional Searching Problems
- Decision procedures for real and p‐adic fields
- Cylindrical Algebraic Decomposition I: The Basic Algorithm
- On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
- Title not available (Why is that?)
- A linear algorithm for computing the visibility polygon from a point
- Some techniques for geometric searching with implicit set representations
- Searching and storing similar lists
Cited In (17)
- Algorithms for bichromatic line-segment problems and polyhedral terrains
- Efficient algorithm for computing the triangle maximizing the length of its smallest side inside a convex polygon
- Robust Point-Location in Generalized Voronoi Diagrams
- Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time.
- Peeling potatoes near-optimally in near-linear time
- Title not available (Why is that?)
- Algorithms of placing recovery points
- Efficient randomized algorithms for some geometric optimization problems
- A singly exponential stratification scheme for real semi-algebraic varieties and its applications
- Large \(k\)-gons in a 1.5D terrain
- Efficient evaluation of specific queries in constraint databases
- Algorithms for location problems based on angular distances
- Title not available (Why is that?)
- Ray shooting on triangles in 3-space
- Title not available (Why is that?)
- Generalized comparison trees for point-location problems
- A note on point location in arrangements of hyperplanes
This page was built for publication: An algorithm for generalized point location and its applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2639635)
