We present a planar point location structure for a convex subdivision S. Given a query sequence of length m, the total running time is O(OPT + m log log n + n), where n is the number of vertices in S and OPT is the minimum running time to process the same query sequence by any linear decision tree for answering planar point location queries in S. The running time includes the preprocessing time. Therefore, for m ≥ n, our running time is only worse than the best possible bound by O(log log n) per query, which is much smaller than the O(log n) query time offered by an worst-case optimal planar point location structure.
展开▼
机译：我们介绍了一个凸形细分S的平面点位置结构。给定长度M的查询序列，总运行时间是O（opt + m log log n + n），其中n是s和opt的顶点数量通过任何线性决策树处理相同的查询序列的最小运行时间，用于在S中应答平面点位置查询。运行时间包括预处理时间。因此，对于M≥N，我们的运行时间仅比每个查询的O（日志Log N）绑定的最佳可能绑定，这远小于由最坏情况最佳平面点提供的O（log n）查询时间位置结构。
展开▼
