2018/10/01 by Siu-Wing Cheng, Cheng, Siu-Wing, Man-Kit Lau +1
Computer Science · Engineering · #Advanced Image and Video Retrieval Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Robotics and Sensor-Based Localization
paper · pdf · doi:10.48550/arxiv.1810.00715
openalex publication_date 2018/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present self-adjusting data structures for answering point location queries in convex and connected subdivisions. Let n be the number of vertices in a convex or connected subdivision. Our structures use O(n) space. For any convex subdivision S, our method processes any online query sequence σ in O(OPT + n) time, where OPT is the minimum time required by any linear decision tree for answering point location queries in S to process σ. For connected subdivisions, the processing time is O(OPT + n + |σ|log(log^* n)). In both cases, the time bound includes the O(n) preprocessing time.