An algorithm for generalized point location and its applications

DOI10.1016/S0747-7171(08)80065-XMaRDI QIDQ2639635zbMATH OpenFDO

Authors Bernard Chazelle, Micha Sharir

Publication date 1990

Published in Journal of Symbolic Computation (Search for Journal in Brave)

zbMATH Keywords

point locationmultidimensional searchinglogarithmic query timeCollins' classical quantifier elimination procedurehigher-dimensional space

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4074477
• scientific article; zbMATH DE number 140454
• scientific article; zbMATH DE number 1182923
• A new point-location algorithm and its practical efficiency: comparison with existing algorithms
• Point location in arrangements of hyperplanes

Cites work

• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 3711282 (Why is no real title available?)
• scientific article; zbMATH DE number 3497890 (Why is no real title available?)
• scientific article; zbMATH DE number 3050844 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• A linear algorithm for computing the visibility polygon from a point
• A new decision method for elementary algebra
• An inequality for the discriminant of a polynomial
• Cylindrical Algebraic Decomposition I: The Basic Algorithm
• Decision procedures for real and p‐adic fields
• Multidimensional Searching Problems
• New applications of random sampling in computational geometry
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• On Euclid's Algorithm and the Theory of Subresultants
• On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
• On the Betti Numbers of Real Varieties
• On the computational power of pushdown automata
• Optimal Point Location in a Monotone Subdivision
• Searching and storing similar lists
• Some dynamic computational geometry problems
• Some techniques for geometric searching with implicit set representations
• Visibility and intersection problems in plane geometry
• -nets and simplex range queries

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
• Algorithms of placing recovery points
• scientific article; zbMATH DE number 5263334 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 3978403 (Why is no real title available?)
• Ray shooting on triangles in 3-space
• scientific article; zbMATH DE number 1779434 (Why is no real title available?)
• 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)