A time-optimal solution to planar point location in ordered functional domains, with applications

Consider a family C of continuous functions stored, in discretized form, one function per row in a mesh with multiple broadcasting of size √n×√n. In a number of Computer Aided Geometric Design applications it is necessary to answer point location queries with respect to the given functions: e.g. cubic B-splines, control polygons of Bezier curves, etc. The main contribution of this work is to show that in such a domain an arbitrary collection of m, (1⩽m⩽n), point location queries can be answered in Θ(m/√n) time. We show that this is best possible on this platform. Our algorithms do not ignore the I/O time and see it as an important component of the overall processing time. In this regard, our algorithms feature a very attractive property, namely that the I/O time and the processing time are essentially the same