Adaptive Planar Point Location

DOI10.1137/18M1218194OpenAlexW3180328527MaRDI QIDQ5009786

Siu-Wing Cheng, Man-Kit Lau

Publication date: 6 August 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.00715

zbMATH Keywords

static optimalityplanar point locationquery distribution

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05) General topics in the theory of algorithms (68W01)

Cites Work

• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• On-line construction of the convex hull of a simple polyline
• Triangulating a simple polygon in linear time
• Ray shooting in polygons using geodesic triangulations
• Expected asymptotically optimal planar point location
• A simple entropy-based algorithm for planar point location
• Instance-Optimal Geometric Algorithms
• Entropy, triangulation, and point location in planar subdivisions
• Optimal Point Location in a Monotone Subdivision
• Self-adjusting binary search trees
• Optimal Search in Planar Subdivisions
• On the Exact Worst Case Query Complexity of Planar Point Location
• A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
• Adaptive Point Location in Planar Convex Subdivisions
• Optimal Expected-Case Planar Point Location
• Dynamic Distribution-Sensitive Point Location